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

MaRDI QIDQ6279342zbMATH OpenFDO

Authors Lucy Ham, Marcel Jackson

Publication date 3 November 2016

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Automorphisms and endomorphisms of algebraic structures (08A35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A finite constraint language $mathscrR$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $operatornameCSP(mathscrR)$ 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 $extttPeqextttNP$, 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.

This page was built for publication: All or nothing: toward a promise problem dichotomy for constraint problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6279342)