Exponential lower bounds for the pigeonhole principle
From MaRDI portal
Publication:687506
DOI10.1007/BF01200117zbMath0784.03034WikidataQ56812988 ScholiaQ56812988MaRDI QIDQ687506
Russell Impagliazzo, Toniann Pitassi, P. W. Beame
Publication date: 18 October 1993
Published in: Computational Complexity (Search for Journal in Brave)
Combinatorics in computer science (68R05) Boolean functions (06E30) Complexity of proofs (03F20) Theory of computing (68Q99)
Related Items (47)
Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings ⋮ Approximate counting and NP search problems ⋮ Unnamed Item ⋮ Approximate Euler characteristic, dimension, and weak pigeonhole principles ⋮ Some remarks on lengths of propositional proofs ⋮ Simplified lower bounds for propositional proofs ⋮ Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ An exponential separation between the parity principle and the pigeonhole principle ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Unnamed Item ⋮ Towards NP-P via proof complexity and search ⋮ Why Extension-Based Proofs Fail ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ Algebraic proof systems over formulas. ⋮ A note on propositional proof complexity of some Ramsey-type statements ⋮ Unnamed Item ⋮ Algebraic proofs over noncommutative formulas ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ Lifting lower bounds for tree-like proofs ⋮ A new proof of the weak pigeonhole principle ⋮ On meta complexity of propositional formulas and propositional proofs ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ Where pigeonhole principles meet Koenig lemmas ⋮ A form of feasible interpolation for constant depth Frege systems ⋮ Exponential lower bounds for the pigeonhole principle ⋮ Partially definable forcing and bounded arithmetic ⋮ Unnamed Item ⋮ Upper bounds on complexity of Frege proofs with limited use of certain schemata ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies ⋮ The Complexity of Propositional Proofs ⋮ Resolution with counting: dag-like lower bounds and different moduli ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Proof Complexity of Non-classical Logics ⋮ Satisfiability via Smooth Pictures ⋮ Propositional proof complexity ⋮ On transformations of constant depth propositional proofs ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Unnamed Item ⋮ Separation results for the size of constant-depth propositional proofs ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Witnessing functions in bounded arithmetic and search problems ⋮ LA, permutations, and the Hajós calculus ⋮ Reflections on Proof Complexity and Counting Principles
Cites Work
- Unnamed Item
- Exponential lower bounds for the pigeonhole principle
- Lower bounds for recognizing small cliques on CRCW PRAM's
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The intractability of resolution
- The deduction rule and linear and near-linear proof simulations
- Parity, circuits, and the polynomial-time hierarchy
- Polynomial size proofs of the propositional pigeonhole principle
- Hard examples for resolution
- Approximation and Small-Depth Frege Proofs
- The relative efficiency of propositional proof systems
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Optimal bounds for decision problems on the CRCW PRAM
This page was built for publication: Exponential lower bounds for the pigeonhole principle
