Propositional proof complexity: an introduction
From MaRDI portal
Recommendations
- The Complexity of Propositional Proofs
- The Complexity of Propositional Proofs
- scientific article; zbMATH DE number 1156870
- scientific article; zbMATH DE number 1860672
- Propositional proof complexity
- Complexity of propositional proofs (invited talk)
- scientific article; zbMATH DE number 3313427
- scientific article; zbMATH DE number 1179974
- scientific article; zbMATH DE number 65760
- scientific article; zbMATH DE number 1860652
Cited in
(19)- Short proofs of the Kneser-Lovász coloring principle
- Quasipolynomial size proofs of the propositional pigeonhole principle
- Analyzing read-once cutting plane proofs in Horn systems
- Minimum propositional proof length is NP-hard to linearly approximate
- Propositional proofs in Frege and extended Frege systems (abstract)
- NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
- Short proofs of the Kneser-Lovász coloring principle
- Proof theory for reasoning with Euler diagrams: a logic translation and normalization
- Towards NP-P via proof complexity and search
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
- scientific article; zbMATH DE number 1860652 (Why is no real title available?)
- scientific article; zbMATH DE number 1390276 (Why is no real title available?)
- Substitution and Propositional Proof Complexity
- The complexity of finding read-once NAE-resolution refutations
- The NP search problems of Frege and extended Frege proofs
- Uniform Proof Complexity
- Proving the infeasibility of Horn formulas through read-once resolution
- Interpolants, cut elimination and flow graphs for the propositional calculus
This page was built for publication: Propositional proof complexity: an introduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4263835)
