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 an
ω-categorical template
Γ such that
L reduces to CSP(
Γ) and CSP(
Γ) is in coNP
L
(i.e., the class coNP with an oracle for
L). CSPs with
ω-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 ω-categorical templates with coNP-complete CSPs and ω-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 ω-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 for infinite constraint
languages.