Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PIGEON HOLE PRINCIPLE:
Reports tagged with pigeon hole principle:
TR00-008 | 20th January 2000
Albert Atserias, Nicola Galesi, Ricard Gavaldà

#### Monotone Proofs of the Pigeon Hole Principle

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 ... more >>>

TR00-087 | 14th November 2000
Albert Atserias, Nicola Galesi, Pavel Pudlak

#### Monotone simulations of nonmonotone propositional proofs

We show that an LK proof of size \$m\$ of a monotone sequent (a sequent

that contains only formulas in the basis \$\wedge,\vee\$) can be turned

into a proof containing only monotone formulas of size \$m^{O(\log m)}\$

and with the number of proof lines polynomial in \$m\$. Also we show

... more >>>

ISSN 1433-8092 | Imprint