The complexity of the pigeonhole principle

DOI10.1007/BF01302964zbMATH Open0811.03042OpenAlexW2089534194MaRDI QIDQ1343166FDOQ1343166

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

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

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)

Cites Work

• Hard examples for resolution
• The intractability of resolution
• Title not available (Why is that?)
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Resolution proofs of generalized pigeonhole principles
• Counting $Δ_0$ sets

Cited In (33)

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

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)