1
$\begingroup$

Wikipedia states

A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in which this is not possible.

The first case is that of strongly relational m-consistent problem when the domains contain at most m elements.

This would imply that any problem with domains of size m that is stongly m-consistent, is satisfiable. However on the same page they mention 3-colorability. It is NP-complete and consists of binary constraints on variables with domain size 3. Generally it should be possible to achieve strong-3-consistency in about $O(n^3)$, so the above statement should be wrong as it implies P=NP. What did they mean to say when the wrote the above statement? Or am I interpreting it in a wrong way?

$\endgroup$
1
+100
$\begingroup$

Yes, the quoted statement is correct. Wikipedia gives a proof in the next four sentences that immediately follow the quote you gave.

The constraints that arise from 3-colorability are not strongly relational 3-consistent, so the quoted statement implies nothing about 3-colorability. Consequently, there is no contradiction.

(Why aren't the constraints from 3-colorability strongly relational 3-consistent? Consider a star graph, with a vertex $v$ that is connected to three other vertices $w,x,y$. There is one constraint per edge in the graph: e.g., one constraint that constrains the colors assigned to vertices $v,w$; one for $v,x$; and one for $v,y$. Suppose we have a partial assignment that assigns $w$ the color red, $x$ blue, and $y$ green. Then there is no way to assign a color to $v$ that makes the three constraints for $vw$, $vx$, and $vy$ all valid. Thus, the constraints do not satisfy the definition of strongly relational 3-consistency.)

$\endgroup$
  • $\begingroup$ I see now. Many times strongly relational i-consistency cannot be achieved with only binary constraints. $\endgroup$ – Albert Hendriks Mar 22 '17 at 6:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.