Conference Proceedings

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.

University of Melbourne Researchers

Citation metrics