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

DOI10.1006/inco.2002.3114zbMath1012.03058OpenAlexW2041857712WikidataQ60512223 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

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

Related Items (12)

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

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

This page was built for publication: Lower bounds for the weak pigeonhole principle and random formulas beyond resolution