Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
DOI10.1007/S10472-014-9407-9zbMATH Open1357.68205OpenAlexW2086971834MaRDI QIDQ457253FDOQ457253
Authors: Bistra Dilkina, Carla P. Gomes, 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
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic in artificial intelligence (68T27)
Cites Work
- Theory and Applications of Satisfiability Testing
- SATLIB: An online resource for research on SAT
- Non-cooperative games
- Title not available (Why is that?)
- Almost 2-SAT is fixed-parameter tractable
- Symbolic model checking: \(10^{20}\) states and beyond
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Parametrized complexity theory.
- A Sufficient Condition for Backtrack-Free Search
- Renaming a Set of Clauses as a Horn Set
- Title not available (Why is that?)
- Network-based heuristics for constraint-satisfaction problems
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- On the minimality and global consistency of row-convex constraint networks
- Title not available (Why is that?)
- Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Backdoor sets of quantified Boolean formulas
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- A sufficient condition for backtrack-bounded search
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Unit Refutations and Horn Sets
- Backdoors to Combinatorial Optimization: Feasibility and Optimality
- Detecting embedded Horn structure in propositional logic
- Computation of Renameable Horn Backdoors
- Tradeoffs in the Complexity of Backdoor Detection
- Constraint Satisfaction with Bounded Treewidth Revisited
- Backdoors in the Context of Learning
- Recognizing disguised NR(1) instances of the satisfiability problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Backdoors to normality for disjunctive logic programs
- Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning
- Title not available (Why is that?)
- Solving #SAT Using Vertex Covers
- Backdoor sets for DLL subsolvers
Cited In (8)
- Backdoors to Combinatorial Optimization: Feasibility and Optimality
- Answer set solver backdoors
- Backdoors in the Context of Learning
- Backdoors into heterogeneous classes of SAT and CSP
- Solving d-SAT via Backdoors to Small Treewidth
- Backdoor sets for DLL subsolvers
- The opacity of backbones
- Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption
Uses Software
This page was built for publication: Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q457253)
