A combinatorial characterization of resolution width
From MaRDI portal
Publication:2475405
DOI10.1016/j.jcss.2007.06.025zbMath1133.03034OpenAlexW2129413084MaRDI QIDQ2475405
Albert Atserias, Victor Dalmau
Publication date: 11 March 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10230/36435
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (36)
From Small Space to Small Width in Resolution ⋮ Narrow Proofs May Be Maximally Long ⋮ On space and depth in resolution ⋮ On the complexity of resolution with bounded conjunctions ⋮ A note about \(k\)-DNF resolution ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games ⋮ On the speed of constraint propagation and the time complexity of arc consistency testing ⋮ Lower Bound Techniques for QBF Proof Systems ⋮ Space Complexity in Polynomial Calculus ⋮ Unnamed Item ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ A game characterisation of tree-like Q-resolution size ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ The complexity of proving that a graph is Ramsey ⋮ Cliques enumeration and tree-like resolution proofs ⋮ Proof Complexity Meets Algebra ⋮ On semantic cutting planes with very small coefficients ⋮ Cutting planes and the parameter cutwidth ⋮ Partially definable forcing and bounded arithmetic ⋮ The treewidth of proofs ⋮ Space proof complexity for random 3-CNFs ⋮ Resolution Width and Cutting Plane Rank Are Incomparable ⋮ A simplified way of proving trade-off results for resolution ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ A Game Characterisation of Tree-like Q-resolution Size ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ A combinatorial characterization of treelike resolution space ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution ⋮ Short Proofs Are Hard to Find ⋮ Super strong ETH is true for PPSZ with small resolution width ⋮ Total Space in Resolution ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the expressive power of Datalog: tools and a case study.
- The intractability of resolution
- Resolution lower bounds for the weak functional pigeonhole principle.
- Optimality of size-width tradeoffs for resolution
- Conjunctive-query containment and constraint satisfaction
- A complexity gap for tree resolution
- Space bounds for resolution
- On the automatizability of resolution and related propositional proof systems
- Resolution lower bounds for perfect matching principles
- Proofs as Games
- Space Complexity in Propositional Calculus
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Many hard examples for resolution
- Hard examples for resolution
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Finite Variable Logics in Descriptive Complexity Theory
- Short proofs are narrow—resolution made simple
- Space complexity of random formulae in resolution
- Pseudorandom Generators in Propositional Proof Complexity
- Resolution lower bounds for the weak pigeonhole principle
- On sufficient conditions for unsatisfiability of random formulas
This page was built for publication: A combinatorial characterization of resolution width
