Space complexity of random formulae in resolution

DOI10.1002/RSA.10089zbMATH Open1048.03046OpenAlexW1974070050MaRDI QIDQ4417005FDOQ4417005

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

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

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)

Cites Work

• Short proofs are narrow -- resolution made simple
• Title not available (Why is that?)
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Title not available (Why is that?)
• Space complexity in propositional calculus

Cited In (20)

• On the complexity of resolution with bounded conjunctions
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• Space proof complexity for random 3-CNFs
• On semantic cutting planes with very small coefficients
• A simplified way of proving trade-off results for resolution
• An Introduction to Lower Bounds on Resolution Proof Systems
• Total space in resolution
• Narrow Proofs May Be Maximally Long
• 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
• Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers
• Supercritical Space-Width Trade-offs for Resolution
• Cumulative Space in Black-White Pebbling and Resolution
• From Small Space to Small Width in Resolution
• A framework for space complexity in algebraic proof systems
• An Upper Bound on the Space Complexity of Random Formulae in Resolution
• LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE

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)