An exponential separation between the parity principle and the pigeonhole principle

DOI10.1016/0168-0072(96)83747-XzbMath0866.03029OpenAlexW2035926913MaRDI 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 boundperfect matchingFrege proofspigeonhole principleoracle separationscombinatorial parity principlesearch classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (20)

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

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

This page was built for publication: An exponential separation between the parity principle and the pigeonhole principle