Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles

DOI10.1137/S0097539703433146zbMath1079.03048OpenAlexW2151373762MaRDI QIDQ4651534

Joshua Buresh-Oppenheim, Ran Raz, Toniann Pitassi, Ashish Sabharwal, P. W. Beame

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703433146

zbMATH Keywords

propositional proof complexitypigeonhole principlebounded-depth Frege proofsquasi-polynomial lower bound

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

This page was built for publication: Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles