Near optimal seperation of tree-like and general resolution
DOI10.1007/S00493-004-0036-5zbMATH Open1063.03043OpenAlexW2092984557MaRDI QIDQ558312FDOQ558312
Authors: Eli Ben-Sasson, Russell Impagliazzo, A. Wigderson 
Publication date: 5 July 2005
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-004-0036-5
Recommendations
- A characterization of tree-like resolution size
- A near-optimal separation of regular and general resolution
- A lower bound for tree resolution
- Separation algorithm for tree partitioning inequalities
- A complexity gap for tree resolution
- Optimal partition trees
- Optimal partition trees
- Tree approximation and optimal encoding
- Optimal multiway generalized split trees
- Treewidth reduction for constrained separation and bipartization problems
automated theorem provinggeneral resolution refutationsnear optimal seperationpolynomial run-timetree-like resolution refutations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)
Cited In (30)
- Short proofs are narrow -- resolution made simple
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- The state of SAT
- The Complexity of Propositional Proofs
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- A proof builder for Max-SAT
- On the relative complexity of resolution refinements and cutting planes proof systems
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- On semantic cutting planes with very small coefficients
- MaxSAT Resolution and Subcube Sums
- On (simple) decision tree rank
- Title not available (Why is that?)
- Regular and General Resolution: An Improved Separation
- A tutorial on time and space bounds in tree-like resolution
- A note about \(k\)-DNF resolution
- The complexity of resolution refinements
- A characterization of tree-like resolution size
- Reversible pebble games and the relation between tree-like and general resolution space
- Resolution over linear equations modulo two
- Finding a tree structure in a resolution proof is NP-complete
- A near-optimal separation of regular and general resolution
- On the automatizability of resolution and related propositional proof systems
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- An Exponential Lower Bound for Width-Restricted Clause Learning
- The depth of resolution proofs
- Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search
- Proofs and Certificates for Max-SAT
- Cliques enumeration and tree-like resolution proofs
- Title not available (Why is that?)
This page was built for publication: Near optimal seperation of tree-like and general resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558312)
