Melissa Antonelli (Department of Computer Science – University of Helsinki) will lead a Philtech seminar titled
On counting propositional logic and Wagner’s
The seminar will be held on October 02, 2025, 15:00 – 17:00 at Sala Martinetti – Via Festa del Perdono 7 – Milan.
Interactions between logic and computer science have been deeply investigated in the last century, but, surprisingly, the study of probabilistic computation was only marginally touched by such fruitful interchanges. The goal of our study is precisely that of start bridging this gap by developing logical systems corresponding to specific aspects of randomized computation and by generalizing standard achievements to the probabilistic realm. To do so, the key ingredient is the introduction of new, measure-sensitive quantifiers associated with quantitative interpretations. In this talk, we will present an extension of classical propositional logic via counting quantifiers, intuitively expressing that a formula is true in a certain portion of its possible interpretations. This logic, not only admits a sound and complete proof system, but is also shown to be related with counting complexity classes. In particular, it is proved that the complexity of deciding the validity of counting formulas in (a special) prenex normal form perfectly matches the corresponding level of the counting hierarchy, a hierarchy of complexity classes introduced by Wagner in 1984/86 as a generalization of Meyer and Stockmeyer’s one and able to express the complexity of many natural problems in which counting is involved.
