Lower bounds for the weak pigeonhole principle and random formulas beyond resolution

DOI10.1006/inco.2002.3114zbMath1012.03058WikidataQ60512223 ScholiaQ60512223MaRDI QIDQ1854546

Maria Luisa Bonet, Juan Luis Esteban, Albert Atserias

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3dba7df9fea3bc9f7f89d6d2c124ef467de7894a

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03F20: Complexity of proofs

Related Items

Resolution and the binary encoding of combinatorial principles, The Complexity of Propositional Proofs, LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE, Lower bounds for \(k\)-DNF resolution on random 3-CNFs, Mean-payoff games and propositional proofs, Short propositional refutations for dense random 3CNF formulas, Resolution over linear equations and multilinear proofs, On the automatizability of resolution and related propositional proof systems, On the complexity of resolution with bounded conjunctions, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Separation results for the size of constant-depth propositional proofs, On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution

Cites Work

• Unnamed Item
• Unnamed Item
• Resolution proofs of generalized pigeonhole principles
• The intractability of resolution
• The monotone circuit complexity of Boolean functions
• On the weak pigeonhole principle
• The Efficiency of Resolution and Davis--Putnam Procedures
• Many hard examples for resolution
• Resolution lower bounds for the weak pigeonhole principle
• Polynomial size proofs of the propositional pigeonhole principle
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Short proofs are narrow—resolution made simple
• Regular resolution lower bounds for the weak pigeonhole principle
• A new proof of the weak pigeonhole principle