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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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$

Improve this answer
$\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.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.