Proof Complexity

DOI10.1017/9781108242066MaRDI QIDQ4629797zbMATH OpenOpenAlexFDO

Authors Jan Krajíček

Publication date 28 March 2019

Full work available at URL https://doi.org/10.1017/9781108242066

Mathematics Subject Classification ID

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)

Recommendations

• scientific article; zbMATH DE number 1860652
• scientific article; zbMATH DE number 819737
• The Complexity of Propositional Proofs
• Logical foundations of proof complexity
• scientific article; zbMATH DE number 5845490

Cited in

(39)

• Proof Complexity Meets Algebra
• Substitution and Propositional Proof Complexity
• Proof Complexity and the Kneser-Lovász Theorem
• The canonical pairs of bounded depth Frege systems
• Proof complexity of modal resolution
• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Perfect matching in random graphs is as hard as Tseitin
• scientific article; zbMATH DE number 4095440 (Why is no real title available?)
• Constructive separations and their consequences
• Lower bounds for QCDCL via formula gauge
• Towards Uniform Certification in QBF
• The Complexity of Propositional Proofs
• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
• scientific article; zbMATH DE number 2212138 (Why is no real title available?)
• On computing small variable disjunction branch-and-bound trees
• scientific article; zbMATH DE number 7753415 (Why is no real title available?)
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• scientific article; zbMATH DE number 7471677 (Why is no real title available?)
• Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
• INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
• scientific article; zbMATH DE number 2161249 (Why is no real title available?)
• Extended Nullstellensatz proof systems
• 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
• Algorithm analysis through proof complexity
• QBF merge resolution is powerful but unnatural
• INTERLEAVING LOGIC AND COUNTING
• On the complexity of finding shortest variable disjunction branch-and-bound proofs
• ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
• scientific article; zbMATH DE number 7561740 (Why is no real title available?)
• Propositional proof complexity
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• A simple proof of QBF hardness
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Unprovability of strong complexity lower bounds in bounded arithmetic
• 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)