Propositional proof complexity
From MaRDI portal
(Redirected from Publication:6064569)
Propositional proof complexity (scientific article; zbMATH DE number 7763400)
Propositional proof complexity (scientific article; zbMATH DE number 7763400)
Summary: Propositional proof complexity studies efficient provability of those statements that can be expressed in propositional logic, in various proof systems, and under various notions of ``efficiency. Proof systems and statements of interest come from a variety of sources that, besides logic and combinatorics, include many other areas like combinatorial optimization and practical SAT solving. This article is an expanded version of the ECM talk in which we will attempt to convey some basic ideas underlying this vibrant area. For the entire collection see [Zbl 1519.00033].
Recommendations
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A generalized method for proving polynomial calculus degree lower bounds
- A new proof of the weak pigeonhole principle
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Automating resolution is NP-hard
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
- Clique Is Hard on Average for Regular Resolution
- Exponential lower bounds for the pigeonhole principle
- Hard examples for bounded depth frege
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 1223618 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1263206 (Why is no real title available?)
- scientific article; zbMATH DE number 1789924 (Why is no real title available?)
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- scientific article; zbMATH DE number 2087215 (Why is no real title available?)
- scientific article; zbMATH DE number 1834646 (Why is no real title available?)
- scientific article; zbMATH DE number 1916823 (Why is no real title available?)
- scientific article; zbMATH DE number 806744 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- scientific article; zbMATH DE number 7561762 (Why is no real title available?)
- scientific article; zbMATH DE number 3313427 (Why is no real title available?)
- scientific article; zbMATH DE number 2243370 (Why is no real title available?)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Logical Foundations of Proof Complexity
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds for the polynomial calculus
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds to the size of constant-depth propositional proofs
- Many hard examples for resolution
- On CDCL-based proof systems with the ordered decision strategy
- Pebble games, proof complexity, and time-space trade-offs
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Proof Complexity
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Random CNF's are hard for the polynomial calculus
- Regular resolution lower bounds for the weak pigeonhole principle
- Resolution lower bounds for perfect matching principles
- Resolution lower bounds for the weak pigeonhole principle
- Resolution with counting: dag-like lower bounds and different moduli
- Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
- Short proofs are narrow—resolution made simple
- The intractability of resolution
- The relative efficiency of propositional proof systems
Cited in
(8)- scientific article; zbMATH DE number 1342249 (Why is no real title available?)
- scientific article; zbMATH DE number 1860652 (Why is no real title available?)
- Substitution and Propositional Proof Complexity
- Reflections on Proof Complexity and Counting Principles
- scientific article; zbMATH DE number 2212138 (Why is no real title available?)
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- The strength of the dominance rule
- Proof complexity of modal resolution
This page was built for publication: Propositional proof complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6064569)
