Monotone Proofs of the Pigeon Hole Principle
From MaRDI portal
Publication:2765569
DOI<461::AID-MALQ461>3.0.CO;2-B 10.1002/1521-3870(200111)47:4<461::AID-MALQ461>3.0.CO;2-BzbMath0989.03065MaRDI 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
proof complexity; geometric logic; pigeonhole principle; Frege proof system; monotone Boolean formula; monotone proofs; threshold formula
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
Expander Construction in VNC1, Monotone simulations of non-monotone proofs., Expander construction in \(\mathrm{VNC}^1\), Proofs with monotone cuts