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

Abstract

A finite constraint language $\mathcal{R}$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $\mathrm{CSP}(\mathcal{R})$ can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions: where 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. For example, subject to the assumption $\text{P}\ne \text{NP}$, then for any~$k$, we show that there is no polynomial time algorithm that can distinguish non-$3$-colourable graphs, from those for which any reasonable $3$-colouring of any $k$ of the vertices can extend to a full $3$-colouring. Our main result shows that an analogous statement holds for all known intractable constraint problems over fixed finite constraint languages.

Updated from version 1 to include new results. Updated from version 2 by some amendments and streamlined arguments

References in corpus (1)

• Asking the metaquestions in constraint tractability

Cited by in corpus (1)

• Axiomatisability and hardness for universal Horn classes of hypergraphs