The complexity of the pigeonhole principle
From MaRDI portal
Publication:1343166
DOI10.1007/BF01302964zbMath0811.03042OpenAlexW2089534194MaRDI QIDQ1343166
Publication date: 1 February 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01302964
First-order arithmetic and fragments (03F30) Classical propositional logic (03B05) Complexity of proofs (03F20)
Related Items
The proof complexity of linear algebra, Circuit principles and weak pigeonhole variants, Simplified lower bounds for propositional proofs, \(\text{Count}(q)\) does not imply \(\text{Count}(p)\), An exponential separation between the parity principle and the pigeonhole principle, NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN, Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms, Tractability of cut-free Gentzen type propositional calculus with permutation inference, The complexity of the Hajós calculus for planar graphs, A generalization of the second incompleteness theorem and some exceptions to it, The Complexity of Propositional Proofs, On the correspondence between arithmetic theories and propositional proof systems – a survey, Proof Complexity of Non-classical Logics, Non-clausal redundancy properties, Tight rank lower bounds for the Sherali-Adams proof system, Random resolution refutations, Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs, Bounded-depth Frege complexity of Tseitin formulas for all graphs, Covered clauses are not propagation redundant, Bounds in the theory of finite covers, Two party immediate response disputes: Properties and efficiency
Cites Work
