On space and depth in resolution

DOI10.1007/S00037-017-0163-1MaRDI QIDQ1616620zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

resolution proofssupercritical tradeoffvariable and total space

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

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)