All or nothing: Toward a promise problem dichotomy for constraint problems

Abstract

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.