2
$\begingroup$

(CSP = "constraint satisfaction problem")

CSPs for which either the variables are restricted to less than two values or the constraints
take less than two inputs are obviously trivial, and Schaefer's dichotomy theorem
gives the complete situation for variables with two possible values.
How hard is it to solve CSPs with 2-variable constraints
but variables that can take more than two values?

$\endgroup$
4
$\begingroup$

With 3 values and binary relations, the CSP is still NP-complete (it is denoted with (3,2)-CSP). A quick reduction is from graph coloring:

add a variable $x_i \in \{1,2,3\}$ for each node; then for each edge $(x_i,x_j)$ add the constraint $x_i \neq x_j$

$\endgroup$
2
$\begingroup$

Schöning's algorithm runs in time $O\left(\left(\frac{d(k-1)}{k}\right)^n\right)$, where $k$ is the clause width and $d$ is the number of possible values per variable.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy