All or nothing: toward a promise problem dichotomy for constraint problems
| Autor: | Ham, Lucy, Jackson, Marcel |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A finite constraint language $\mathscr{R}$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $\operatorname{CSP}(\mathscr{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 $\texttt{P}\neq \texttt{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. Comment: Updated from version 1 to include new results. Updated from version 2 by some amendments and streamlined arguments |
| Databáze: | arXiv |
| Externí odkaz: |
|