All or nothing: Toward a promise problem dichotomy for constraint problems
L Ham, M Jackson
Principles and Practice of Constraint Programming | Springer | Published : 2017
We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions. The instances are guaranteed to either have no solutions at all, or to be k-robustly satisfiable (for any fixed k), meaning that every “reasonable” partial instantiation on k variables extends to a solution.