Supercritical space-width trade-offs for resolution
From MaRDI portal
(Redirected from Publication:5215515)
Supercritical space-width trade-offs for resolution (scientific article; zbMATH DE number 7166152)
Supercritical space-width trade-offs for resolution (scientific article; zbMATH DE number 7166152)
Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)
Recommendations
- Supercritical space-width trade-offs for resolution
- On space and depth in resolution
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- From small space to small width in resolution
Cites work
- A combinatorial characterization of resolution width
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- A Machine-Oriented Logic Based on the Resolution Principle
- A new kind of tradeoffs in propositional proof complexity
- A tradeoff between length and width in resolution
- GRASP: a search algorithm for propositional satisfiability
- Hard examples for resolution
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 3029852 (Why is no real title available?)
- Many hard examples for resolution
- Narrow proofs may be maximally long
- Narrow proofs may be spacious: separating space and width in resolution
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- Pebble games, proof complexity, and time-space trade-offs
- Short proofs are narrow—resolution made simple
- Size-space tradeoffs for resolution
- Some trade-off results for polynomial calculus (extended abstract)
- Space bounds for resolution
- Space Complexity in Propositional Calculus
- Space complexity of random formulae in resolution
- Space proof complexity for random 3-CNFs
- The efficiency of resolution and Davis-Putnam procedures
- The intractability of resolution
- The relative efficiency of propositional proof systems
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Total space in resolution
- Total space in resolution is at least width squared
- Towards an optimal separation of space and length in resolution
Cited in
(12)- On space and depth in resolution
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- From small space to small width in resolution
- Supercritical space-width trade-offs for resolution
- Super strong ETH is true for PPSZ with small resolution width
- On the Capacity of the Precision-Resolution System
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Polynomial calculus space and resolution width
- Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
- On the power and limitations of branch and cut
- Supercritical size-width tree-like resolution trade-offs for graph isomorphism
This page was built for publication: Supercritical space-width trade-offs for resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215515)
