A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
From MaRDI portal
Publication:3502705
DOI10.1007/978-3-540-79719-7_16zbMath1138.68543OpenAlexW2114975369MaRDI QIDQ3502705
Michael Kaufmann, Carsten Sinz, Stephan Kottler
Publication date: 27 May 2008
Published in: Theory and Applications of Satisfiability Testing – SAT 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-79719-7_16
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Backdoors for linear temporal logic ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ On Some Aspects of Mixed Horn Formulas ⋮ Backdoors to tractable answer set programming
Cites Work
- An improved deterministic local search algorithm for 3-SAT
- Satisfiability of mixed Horn formulas
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- On good algorithms for determining unsatisfiability of propositional formulas
- Matched Formulas and Backdoor Sets
- Theory and Applications of Satisfiability Testing
- Solving #SAT Using Vertex Covers
- Unnamed Item