Backdoors into heterogeneous classes of SAT and CSP.

Serge Gaspers Neeldhara Misra Sebastian Ordyniak Stefan Szeider Stanislav Zivný

Published in: J. Comput. Syst. Sci. (2017)

Keyphrases

satisfiability problem
sat solvers
sat problem
sat instances
constraint satisfaction problems
sat encodings
tractable classes
np complete

constraint satisfaction
backtracking search
search algorithm
boolean satisfiability
sat solving
random instances
propositional satisfiability

constraint solving
max sat
hidden structure
arc consistency
stochastic local search algorithms
randomly generated
unit propagation

tree decompositions
clause learning
boolean formula
constraint propagation
search strategies
constraint programming
search space