Space complexity of random formulae in resolution

DOI10.1002/RSA.10089MaRDI QIDQ4417005zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Nicola Galesi

Publication date 6 August 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.10089

zbMATH Keywords

lower bounds on the clause spacematching games on bipartite graphsspace complexity of refuting unsatisfiable random formulastreelike resolution refutations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Games involving graphs (91A43) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• An Upper Bound on the Space Complexity of Random Formulae in Resolution
• Space proof complexity for random 3-CNFs
• scientific article; zbMATH DE number 1775444
• Total space in resolution
• Space bounds for resolution

Cites work

• scientific article; zbMATH DE number 1424047 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Short proofs are narrow -- resolution made simple
• Space complexity in propositional calculus

Cited in

(21)

• On the complexity of resolution with bounded conjunctions
• Perfect matching in random graphs is as hard as Tseitin
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Space proof complexity for random 3-CNFs
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• A simplified way of proving trade-off results for resolution
• On semantic cutting planes with very small coefficients
• Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
• An Introduction to Lower Bounds on Resolution Proof Systems
• Cumulative space in black-white pebbling and resolution
• Trade-offs between time and memory in a tighter model of CDCL SAT solvers
• Total space in resolution
• From small space to small width in resolution
• On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
• A combinatorial characterization of resolution width
• Space Complexity in Polynomial Calculus
• The resolution complexity of random graph \(k\)-colorability
• Supercritical space-width trade-offs for resolution
• Narrow proofs may be maximally long
• A framework for space complexity in algebraic proof systems
• An Upper Bound on the Space Complexity of Random Formulae in Resolution

This page was built for publication: Space complexity of random formulae in resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4417005)