Hard constraint satisfaction problems have hard gaps at location 1.

Peter Jonsson Andrei A. Krokhin Fredrik Kuivinen

Published in: Theor. Comput. Sci. (2009)

Keyphrases

constraint satisfaction problems
constraint satisfaction
constraint programming
constraint propagation
combinatorial problems
graph coloring problems
search space
np complete
global constraints
constraint solving
random instances
non binary
pseudo boolean optimization