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.68205MaRDI 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
68T05: Learning and adaptive systems in artificial intelligence
68T27: Logic in artificial intelligence
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
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
