Sulle logiche counting e la gerarchia di Wagner

Primo seminario del ciclo DAReLOGICA

Organizzato da: Melissa Antonelli, Guido Gherardi, Eugenio Orlandelli


È noto che esistano molteplici e profonde interazioni tra la logica e l'informatica teorica e che, storicamente, lo sviluppo dei modelli di computazione abbia fortemente beneficiato del loro studio. D'altra parte, inaspettatamente, la computazione probabilistica è stata toccata solo marginalmente da questi fruttuosi scambi. Il lavoro che presenterà si colloca all'interno di un progetto che intende (iniziare a) colmare questa lacuna introducendo logiche intrinsecamente quantitative e investigando la loro interazione con specifici aspetti della computazione probabilistica. In particolare, ci si concentrerà sul rapporto tra logica e complessità: verranno introdotte le cosiddette "logiche proposizionali counting" - definite estendendo il linguaggio della logica proposizionale classica con quantificatori capaci di esprimere che una formula sia vera "con una certa probabilità" - e si mostrerà che il problema della validità per le formule di questa logica (in una data forma) caratterizza esattamente il livello corrispondente della gerarchia di Wagner.