Lifting lower bounds for tree-like proofs
DOI10.1007/S00037-013-0064-XzbMATH Open1341.03087OpenAlexW2124396273MaRDI QIDQ475337FDOQ475337
Publication date: 26 November 2014
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-013-0064-x
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)
Cites Work
- Title not available (Why is that?)
- Parity, circuits, and the polynomial-time hierarchy
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Short proofs are narrow -- resolution made simple
- The intractability of resolution
- Title not available (Why is that?)
- Non-automatizability of bounded-depth Frege proofs
- Lower bounds to the size of constant-depth propositional proofs
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Exponential lower bounds for the pigeonhole principle
- Bounded arithmetic and the polynomial hierarchy
- An exponential lower bound for the size of monotone real circuits
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Quantified propositional calculi and fragments of bounded arithmetic
- Bounds for proof-search and speed-up in the predicate calculus
Cited In (2)
Recommendations
- The treewidth of proofs 👍 👎
- Lower Bounds for QBFs of Bounded Treewidth 👍 👎
- An improved lower bound for the elementary theories of trees 👍 👎
- Title not available (Why is that?) 👍 👎
- 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 👍 👎
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)
