On space and depth in resolution
From MaRDI portal
Publication:1616620
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
Cites work
- A Machine-Oriented Logic Based on the Resolution Principle
- A combinatorial characterization of resolution width
- A new kind of tradeoffs in propositional proof complexity
- From small space to small width in resolution
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- On the diameter of permutation groups
- On the width of semialgebraic proofs and algorithms
- Pebble games, proof complexity, and time-space trade-offs
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Short proofs are narrow—resolution made simple
- Size-space tradeoffs for resolution
- Some trade-off results for polynomial calculus (extended abstract)
- Space Complexity in Propositional Calculus
- Space bounds for resolution
- Sum-of-squares proofs and the quest toward optimal algorithms
- Supercritical space-width trade-offs for resolution
- The depth of resolution proofs
- The relative efficiency of propositional proof systems
- Total space in resolution is at least width squared
Cited in
(14)- The depth of resolution proofs
- Reversible pebble games and the relation between tree-like and general resolution space
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Resolution-limited measure and dimension
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Size-space tradeoffs for resolution
- 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
- Supercritical space-width trade-offs for resolution
- Supercritical space-width trade-offs for resolution
- A simplified way of proving trade-off results 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)