Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, piano secondo
Aula C2

Abstract:
The main goal of Proof Complexity is the study of the length of proofs in propositional proof systems, a line of research mainly motivated by long-standing open problems in Complexity Theory. After a short introduction to the main concepts of Proof Complexity and a review of the most important results relating Circuit Complexity to Proof Complexity, we will present some recent results for Monotone proof systems:
(1) unlike the case of circuits, monotone proof systems can efficiently simulate nonmonotone ones;
(2) Several combinatorial principles, that initially appeared as good candidates to prove exponential lower bounds in monotone systems, admit proofs of polynomial length.
Papers can be downloaded here