The complexity of the pigeonhole principle

DOI10.1007/BF01302964MaRDI QIDQ1343166zbMATH OpenOpenAlexFDO

Authors Miklós Ajtai

Publication date 1 February 1995

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01302964

zbMATH Keywords

pigeonhole principleunlimited fan-in constant depth polynomial size Boolean formula

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Recommendations

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Some properties of pigeon-hole formulas
• Exponential lower bounds for the pigeonhole principle
• On the weak pigeonhole principle

Cites work

• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• Counting $Δ_0$ sets
• Hard examples for resolution
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Resolution proofs of generalized pigeonhole principles
• The intractability of resolution

Cited in

(33)

• An exponential separation between the parity principle and the pigeonhole principle
• Circuit principles and weak pigeonhole variants
• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
• Some properties of pigeon-hole formulas
• The complexity of the stamp folding problem
• scientific article; zbMATH DE number 5530365 (Why is no real title available?)
• The independence of the modulo \(p\) counting principles
• Simplified lower bounds for propositional proofs
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• Tight rank lower bounds for the Sherali-Adams proof system
• The proof complexity of linear algebra
• Non-clausal redundancy properties
• Exponential lower bounds for the pigeonhole principle
• A generalization of the second incompleteness theorem and some exceptions to it
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Tractability of cut-free Gentzen type propositional calculus with permutation inference
• scientific article; zbMATH DE number 176196 (Why is no real title available?)
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• Count\((q)\) versus the pigeon-hole principle
• Proof complexity of non-classical logics
• On the correspondence between arithmetic theories and propositional proof systems – a survey
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• The complexity of the Hajós calculus for planar graphs
• Covered clauses are not propagation redundant
• Bounds in the theory of finite covers
• The Complexity of Propositional Proofs
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• The Pigeonhole Principle and Fragments of Arithmetic
• Random resolution refutations
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
• Two party immediate response disputes: Properties and efficiency
• Extended Nullstellensatz proof systems

This page was built for publication: The complexity of the pigeonhole principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1343166)