Manuel Bodirsky
Non-dichotomies in Constraint Satisfaction Complexity
With Martin Grohe. In the Proceedings of the International Colloquium on Colloquium on Automata, Languages and Programming (ICALP08).
Abstract
We show that every computational decision problem is polynomial-time equivalent to a constraint satisfaction problem (CSP) with an infinite template. We also construct for every decision problem L a countably categorical template Gamma such that L reduces to CSP(Gamma) and CSP(Gamma) is in coNP^L (i.e., the class coNP with an oracle for L). CSPs with countably categorical templates are of special interest, because the universal-algebraic approach can be applied to study their computational complexity. Furthermore, we prove that there are countably categorical templates with coNP-complete CSPs and countably categorical templates with coNP-intermediate CSPs, i.e., problems in coNP that are neither coNP-complete nor in P (unless P=coNP). To construct the coNP-intermediate CSP with countably categorical template we modify the proof of Ladner's theorem. A similar modification allows us to also prove a non-dichotomy result for a class of left-hand side restricted CSPs, which was left open in [10]. We finally show that if the so-called local-global conjecture for infinite constraint languages (over a finite domain) is false, then there is no dichotomy for the constraint satisfaction problem fo r infinite constraint languages.
Download
Download: a long version in pdf.
