Tradeoffs in the Complexity of Backdoor Detection

DOI10.1007/978-3-540-74970-7_20MaRDI QIDQ3523063zbMATH OpenOpenAlexFDO

Authors Bistra Dilkina, Ashish Sabharwal, Carla P. Gomes

Publication date 2 September 2008

Published in Principles and Practice of Constraint Programming – CP 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74970-7_20

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Upper and lower bounds for weak backdoor set detection
• Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption
• Barriers to black-box constructions of traitor tracing systems
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• Towards defeating backdoored random oracles: indifferentiability with bounded adaptivity
• Backdoors to q-Horn
• Backdoors to q-Horn
• scientific article; zbMATH DE number 2043330

Cites work

• A sufficient condition for backtrack-bounded search
• A Sufficient Condition for Backtrack-Free Search
• Backdoor sets for DLL subsolvers
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Constraint Satisfaction with Bounded Treewidth Revisited
• Detecting embedded Horn structure in propositional logic
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• scientific article; zbMATH DE number 67482 (Why is no real title available?)
• scientific article; zbMATH DE number 2084720 (Why is no real title available?)
• scientific article; zbMATH DE number 956843 (Why is no real title available?)
• Network-based heuristics for constraint-satisfaction problems
• On the minimality and global consistency of row-convex constraint networks
• Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning

Cited in

(16)

• Backdoors for linear temporal logic
• Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption
• Backdoors to tractable answer set programming
• Strong Backdoors for Default Logic
• Backdoors to satisfaction
• Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms
• Computation of Renameable Horn Backdoors
• Backdoors to Combinatorial Optimization: Feasibility and Optimality
• Backdoors in the Context of Learning
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Upper and lower bounds for weak backdoor set detection
• Learning cluster-based structure to solve constraint satisfaction problems
• Backdoor DNFs
• Backdoors into heterogeneous classes of SAT and CSP
• Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability
• Backdoor sets for DLL subsolvers

Describes a project that uses

Uses Software

• Chaff

This page was built for publication: Tradeoffs in the Complexity of Backdoor Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3523063)