Simplified lower bounds for propositional proofs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3904558 (Why is no real title available?)
- scientific article; zbMATH DE number 806753 (Why is no real title available?)
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Approximation and Small-Depth Frege Proofs
- Exponential lower bounds for the pigeonhole principle
- Hard examples for resolution
- Many hard examples for resolution
- Mathematical logic.
- Parity, circuits, and the polynomial-time hierarchy
- The complexity of the pigeonhole principle
Cited in
(13)- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Reflections on Proof Complexity and Counting Principles
- Partially definable forcing and bounded arithmetic
- Lower bounds for bounded depth Frege proofs via Pudlák-Buss games
- Boolean functions on \(S_n\) which are nearly linear
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
- A Logical Autobiography
- Minimum propositional proof length is NP-hard to linearly approximate
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- LA, permutations, and the Hajós calculus
- Random resolution refutations
- Bounded-depth Frege complexity of Tseitin formulas for all graphs
This page was built for publication: Simplified lower bounds for propositional proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1374208)
