Pages that link to "Item:Q4847394"
From MaRDI portal
The following pages link to An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle (Q4847394):
Displayed 47 items.
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Lifting lower bounds for tree-like proofs (Q475337) (← links)
- A note on propositional proof complexity of some Ramsey-type statements (Q627444) (← links)
- Algebraic proofs over noncommutative formulas (Q642520) (← links)
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem (Q647334) (← links)
- On meta complexity of propositional formulas and propositional proofs (Q937212) (← links)
- Simplified lower bounds for propositional proofs (Q1374208) (← links)
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (Q1377580) (← 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)
- Algebraic proof systems over formulas. (Q1401356) (← links)
- Some remarks on lengths of propositional proofs (Q1908815) (← links)
- An exponential separation between the parity principle and the pigeonhole principle (Q1923563) (← links)
- Resolution with counting: dag-like lower bounds and different moduli (Q2029775) (← links)
- Bounded-depth Frege complexity of Tseitin formulas for all graphs (Q2084956) (← links)
- Partially definable forcing and bounded arithmetic (Q2257103) (← links)
- On transformations of constant depth propositional proofs (Q2311211) (← links)
- Random resolution refutations (Q2311546) (← links)
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies (Q2500481) (← links)
- Separation results for the size of constant-depth propositional proofs (Q2566064) (← links)
- Satisfiability via Smooth Pictures (Q2817998) (← links)
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems (Q2944868) (← links)
- Parameterized Bounded-Depth Frege Is Not Optimal (Q3012838) (← links)
- A form of feasible interpolation for constant depth Frege systems (Q3570172) (← links)
- On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
- Witnessing functions in bounded arithmetic and search problems (Q4227882) (← links)
- Forcing in Finite Structures (Q4351930) (← links)
- Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings (Q4527935) (← links)
- Characterizing Propositional Proofs as Noncommutative Formulas (Q4577770) (← links)
- Proof Complexity Meets Algebra (Q4617977) (← links)
- An unexpected separation result in Linearly Bounded Arithmetic (Q4666949) (← links)
- (Q4989407) (← links)
- Reflections on Proof Complexity and Counting Principles (Q5027248) (← links)
- Approximate counting and NP search problems (Q5055313) (← links)
- (Q5077146) (← links)
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs (Q5092411) (← links)
- (Q5136303) (← links)
- Where pigeonhole principles meet Koenig lemmas (Q5158115) (← links)
- (Q5208872) (← links)
- Approximate Euler characteristic, dimension, and weak pigeonhole principles (Q5311719) (← links)
- The Complexity of Propositional Proofs (Q5444711) (← links)
- LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE (Q5501765) (← links)
- (Q5875501) (← links)
- A new proof of the weak pigeonhole principle (Q5894824) (← links)
- Proof Complexity of Non-classical Logics (Q5894972) (← links)
- Propositional proof complexity (Q6064569) (← links)
- Circular (Yet Sound) Proofs in Propositional Logic (Q6116357) (← links)