Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
From MaRDI portal
Publication:457253
DOI10.1007/s10472-014-9407-9zbMath1357.68205OpenAlexW2086971834MaRDI QIDQ457253
Carla P. Gomes, Bistra Dilkina, Ashish Sabharwal
Publication date: 26 September 2014
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-014-9407-9
Learning and adaptive systems in artificial intelligence (68T05) Logic in artificial intelligence (68T27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (2)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Backdoor sets for DLL subsolvers
- Almost 2-SAT is fixed-parameter tractable
- Backdoor sets of quantified Boolean formulas
- Network-based heuristics for constraint-satisfaction problems
- Symbolic model checking: \(10^{20}\) states and beyond
- Detecting embedded Horn structure in propositional logic
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
- Parametrized complexity theory.
- Non-cooperative games
- Computation of Renameable Horn Backdoors
- Tradeoffs in the Complexity of Backdoor Detection
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Constraint Satisfaction with Bounded Treewidth Revisited
- Backdoors to Combinatorial Optimization: Feasibility and Optimality
- Backdoors in the Context of Learning
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- A sufficient condition for backtrack-bounded search
- Recognizing disguised NR(1) instances of the satisfiability problem
- A Sufficient Condition for Backtrack-Free Search
- Unit Refutations and Horn Sets
- Renaming a Set of Clauses as a Horn Set
- On the minimality and global consistency of row-convex constraint networks
- Backdoors to Normality for Disjunctive Logic Programs
- Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning
- Theory and Applications of Satisfiability Testing
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Solving #SAT Using Vertex Covers
This page was built for publication: Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
