On space and depth in resolution
From MaRDI portal
Publication:1616620
DOI10.1007/s00037-017-0163-1OpenAlexW2765538602MaRDI QIDQ1616620
Publication date: 7 November 2018
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-017-0163-1
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (3)
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Reversible pebble games and the relation between tree-like and general resolution space
Cites Work
- The depth of resolution proofs
- On the diameter of permutation groups
- Space bounds for resolution
- A combinatorial characterization of resolution width
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Space Complexity in Propositional Calculus
- A New Kind of Tradeoffs in Propositional Proof Complexity
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Size-Space Tradeoffs for Resolution
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- Sum-of-squares proofs and the quest toward optimal algorithms
- On the Width of Semialgebraic Proofs and Algorithms
- Total Space in Resolution Is at Least Width Squared
- Supercritical Space-Width Trade-offs for Resolution
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- From Small Space to Small Width in Resolution
- Some trade-off results for polynomial calculus
- A Machine-Oriented Logic Based on the Resolution Principle
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
This page was built for publication: On space and depth in resolution
