An exponential separation between the parity principle and the pigeonhole principle

DOI10.1016/0168-0072(96)83747-XzbMath0866.03029MaRDI QIDQ1923563

P. W. Beame, Toniann Pitassi

Publication date: 25 November 1996

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(96)83747-x

zbMATH Keywords

lower bound; perfect matching; Frege proofs; pigeonhole principle; oracle separations; combinatorial parity principle; search classes

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F20: Complexity of proofs

Related Items

Unnamed Item, Unnamed Item, Satisfiability, branch-width and Tseitin tautologies, Propositional proofs and reductions between NP search problems, Two party immediate response disputes: Properties and efficiency, Optimal length resolution refutations of difference constraint systems, An exponential separation between the parity principle and the pigeonhole principle, On the automatizability of polynomial calculus, Space proof complexity for random 3-CNFs, Bounded-depth Frege complexity of Tseitin formulas for all graphs, Propositional proof systems based on maximum satisfiability, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, On transformations of constant depth propositional proofs, Resolution over linear equations modulo two, Width versus size in resolution proofs, Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies, Separation results for the size of constant-depth propositional proofs, Typical forcings, NP search problems and an extension of a theorem of Riis, A Framework for Space Complexity in Algebraic Proof Systems, NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability

Cites Work

• Exponential lower bounds for the pigeonhole principle
• The intractability of resolution
• The complexity of the pigeonhole principle
• An exponential separation between the parity principle and the pigeonhole principle
• Polynomial size proofs of the propositional pigeonhole principle
• Hard examples for resolution
• The relative efficiency of propositional proof systems
• Optimal bounds for decision problems on the CRCW PRAM
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item