Pages that link to "Item:Q1343166"

The following pages link to The complexity of the pigeonhole principle (Q1343166):

Displaying 31 items.

• The complexity of the stamp folding problem (Q391214) (← links)
• Tractability of cut-free Gentzen type propositional calculus with permutation inference (Q672046) (← links)
• Exponential lower bounds for the pigeonhole principle (Q687506) (← links)
• Two party immediate response disputes: Properties and efficiency (Q814510) (← links)
• Tight rank lower bounds for the Sherali-Adams proof system (Q1019183) (← links)
• Count\((q)\) versus the pigeon-hole principle (Q1360313) (← links)
• Simplified lower bounds for propositional proofs (Q1374208) (← links)
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) (Q1377601) (← links)
• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms (Q1401230) (← links)
• Bounds in the theory of finite covers (Q1604371) (← links)
• The proof complexity of linear algebra (Q1886325) (← links)
• An exponential separation between the parity principle and the pigeonhole principle (Q1923563) (← links)
• Non-clausal redundancy properties (Q2055860) (← links)
• Bounded-depth Frege complexity of Tseitin formulas for all graphs (Q2084956) (← links)
• Covered clauses are not propagation redundant (Q2096437) (← links)
• The complexity of the Hajós calculus for planar graphs (Q2268877) (← links)
• Random resolution refutations (Q2311546) (← links)
• Circuit principles and weak pigeonhole variants (Q2383589) (← links)
• A generalization of the second incompleteness theorem and some exceptions to it (Q2500470) (← links)
• The independence of the modulo \(p\) counting principles (Q2817631) (← links)
• Some properties of pigeon-hole formulas (Q2917147) (← links)
• (Q3615559) (← links)
• On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
• The Pigeonhole Principle and Fragments of Arithmetic (Q3688388) (← links)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle (Q4847394) (← links)
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs (Q5092411) (← links)
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN (Q5100043) (← links)
• The Complexity of Propositional Proofs (Q5444711) (← links)
• Proof Complexity of Non-classical Logics (Q5894972) (← links)
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 (Q6613418) (← links)
• Extended Nullstellensatz proof systems (Q6621298) (← links)