On space and depth in resolution
From MaRDI portal
Publication:1616620
DOI10.1007/S00037-017-0163-1OpenAlexW2765538602MaRDI QIDQ1616620FDOQ1616620
Authors: Alexander Razborov 
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
Recommendations
- Towards an optimal separation of space and length in resolution
- scientific article; zbMATH DE number 1304340
- Space bounds for resolution
- scientific article; zbMATH DE number 4090348
- Notes on resolving resolution dimensions
- Size-space tradeoffs for resolution
- Resolving resolution dimensions
- Total space in resolution
- Supercritical space-width trade-offs for resolution
- Supercritical space-width trade-offs for resolution
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Cites Work
- Sum-of-squares proofs and the quest toward optimal algorithms
- A Machine-Oriented Logic Based on the Resolution Principle
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- On the diameter of permutation groups
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Space Complexity in Propositional Calculus
- Space bounds for resolution
- The depth of resolution proofs
- A combinatorial characterization of resolution width
- Size-space tradeoffs for resolution
- Pebble games, proof complexity, and time-space trade-offs
- A new kind of tradeoffs in propositional proof complexity
- 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 (extended abstract)
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Cited In (14)
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- Total space in resolution is at least width squared
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- A simplified way of proving trade-off results for resolution
- Reversible pebble games and the relation between tree-like and general resolution space
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Supercritical space-width trade-offs for resolution
- Supercritical space-width trade-offs for resolution
- The depth of resolution proofs
- Resolution-limited measure and dimension
- Size-space tradeoffs for resolution
- Space bounds for resolution
This page was built for publication: On space and depth in resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1616620)
