From Backdoor Key to Backdoor Completability: Improving a Known Measure of Hardness for the Satisfiable CSP.
Guillaume EscamocherMohamed SialaBarry O'SullivanPublished in: CPAIOR (2018)
Keyphrases
- sat instances
- random instances
- phase transition
- sat problem
- fixed parameter tractable
- satisfiability problem
- randomly generated
- sat solvers
- constraint satisfaction problems
- np complete
- constraint satisfaction
- np hard
- computational problems
- distance measure
- lower bound
- similarity measure
- search tree
- global constraints
- constraint networks
- mutual information
- max sat
- computational complexity