Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
- The treewidth of proofs
- Lower Bounds for QBFs of Bounded Treewidth
- An improved lower bound for the elementary theories of trees
- scientific article; zbMATH DE number 2086919
- Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
- Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
- On topological lower bounds for algebraic computation trees
- A lower bound for tree resolution
- Complexity lower bounds for approximation algebraic computation trees
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
Cites work
- scientific article; zbMATH DE number 953683 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- An exponential lower bound for the size of monotone real circuits
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Bounded arithmetic and the polynomial hierarchy
- Bounds for proof-search and speed-up in the predicate calculus
- Exponential lower bounds for the pigeonhole principle
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds to the size of constant-depth propositional proofs
- Non-automatizability of bounded-depth Frege proofs
- Parity, circuits, and the polynomial-time hierarchy
- Quantified propositional calculi and fragments of bounded arithmetic
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Short proofs are narrow -- resolution made simple
- The intractability of resolution
Cited in
(4)
This page was built for publication: Lifting lower bounds for tree-like proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475337)
