Proof Complexity
From MaRDI portal
Publication:4629797
DOI10.1017/9781108242066OpenAlexW4211118908MaRDI QIDQ4629797FDOQ4629797
Authors: Jan Krajíček 
Publication date: 28 March 2019
Full work available at URL: https://doi.org/10.1017/9781108242066
Recommendations
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Cited In (39)
- Substitution and Propositional Proof Complexity
- Proof Complexity Meets Algebra
- Proof Complexity and the Kneser-Lovász Theorem
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- The canonical pairs of bounded depth Frege systems
- Perfect matching in random graphs is as hard as Tseitin
- Proof complexity of modal resolution
- Title not available (Why is that?)
- Constructive separations and their consequences
- Towards Uniform Certification in QBF
- Lower bounds for QCDCL via formula gauge
- The Complexity of Propositional Proofs
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
- Title not available (Why is that?)
- On computing small variable disjunction branch-and-bound trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- Extended Nullstellensatz proof systems
- Title not available (Why is that?)
- Proof complexity of substructural logics
- On the proof complexity of logics of bounded branching
- Short refutations for an equivalence-chain principle for constant-depth formulas
- QBF merge resolution is powerful but unnatural
- INTERLEAVING LOGIC AND COUNTING
- Algorithm analysis through proof complexity
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Title not available (Why is that?)
- Propositional proof complexity
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- A simple proof of QBF hardness
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Unprovability of strong complexity lower bounds in bounded arithmetic
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- Twelve Problems in Proof Complexity
- Equivalence checking for orthocomplemented bisemilattices in log-linear time
This page was built for publication: Proof Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629797)
