Monotone Proofs of the Pigeon Hole Principle

DOI<461::AID-MALQ461>3.0.CO;2-B 10.1002/1521-3870(200111)47:4<461::AID-MALQ461>3.0.CO;2-BzbMath0989.03065OpenAlexW2031370656MaRDI QIDQ2765569

Albert Atserias, Nicola Galesi, Ricard Gavaldà

Publication date: 16 June 2002

Full work available at URL: https://doi.org/10.1002/1521-3870(200111)47:4<461::aid-malq461>3.0.co;2-b

zbMATH Keywords

proof complexitygeometric logicpigeonhole principleFrege proof systemmonotone Boolean formulamonotone proofsthreshold formula

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (4)

Monotone simulations of non-monotone proofs. ⋮ Proofs with monotone cuts ⋮ Expander Construction in VNC1 ⋮ Expander construction in \(\mathrm{VNC}^1\)

This page was built for publication: Monotone Proofs of the Pigeon Hole Principle