Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Monotone Proofs of the Pigeon Hole Principle

Autor
Galesi, N.; Atserias, A.; Gavaldà, R.
Tipus d'activitat
Article en revista
Revista
Electronic colloquium on computational complexity
Data de publicació
2000-02
Número
TR00-008
Pàgina inicial
1
Pàgina final
13
Resum
We study the complexity of proving the Pigeon Hole Principle (PHP) in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We show that the standard encoding of the PHP as a monotone sequent admits quasipolynomial-size proofs in this system. This result is a consequence of deriving the basic properties of certain quasipolynomial-size monotone formulas computing the boolean threshold functions. Since it is known that the shortest proofs of the PHP in systems such as Resoluti...
Paraules clau
Monotone Calculus, Proof Complexity, Threshold Functions, pigeon hole principle
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
LOGPROG - Lògica i Programació

Participants