Complexity of Constraint Satisfaction - Dichotomy Theorems

Dichotomy Theorems

Some constraint languages (or non-uniform problems) are known to correspond to problems solvable in polynomial time, and some others are known to express NP-complete problems. However, it is possible that some constraint languages are neither. It is known by Ladner's theorem that if P is not equal to NP, then there exist problems in NP that are neither polynomial-time nor NP-hard. As of 2007, it is not known if such problems can be expressed as constraint satisfaction problems with a fixed constraint language. If Ladner languages were not expressible in this way, the set of all constraint languages could be divided exactly into those defining polynomial-time and those defining NP-complete problems; that is, this set would exhibit a dichotomy.

Partial results are known for some sets of constraint languages. The best known such result is Schaefer's dichotomy theorem, which proves the existence of a dichotomy in the set of constraint languages on a binary domain. More precisely, it proves that a relation restriction on a binary domain is tractable if all its relations belong to one of six classes, and is NP-complete otherwise. Bulatov proved a dichotomy theorem for domains of three elements.

Another dichotomy theorem for constraint languages is the Hell-Nesetril theorem, which shows a dichotomy for problems on binary constraints with a single fixed symmetric relation. In terms of the homomorphism problem, every such problem is equivalent to the existence of a homomorphism from a relational structure to a given fixed undirected graph (an undirected graph can be regarded as a relational structure with a single binary symmetric relation). The Hell-Nesetril theorem proves that every such problem is either polynomial-time or NP-complete. More precisely, the problem is polynomial-time if the graph is 2-colorable, that is, it is bipartite, and is NP-complete otherwise.