The Constraint satisfaction problem (CSP) is roughly speaking a formalism that defines a finite set of relations over a domain. The relations are simply defined by enlisting elements in certain constraints.
A CSP can be arc-consistent. But I am struggeling to understand the definition given in my lecture:
A CSP $I=(X,D,C)$ ($X$ is the set of variables, $D$ the domain and $C$ the set of constraints that defines the relations) is arc-consistent if for all variables $x$ there is a constraint $(x,D_x)$ such that
- For all unary constraints $(x,P) \in C$ it holds that $D_x \subseteq P$
- For all binary constraints $((x,y),R) \in C$ it holds that $$D_x \subseteq \{a \mid \exists b \in D_y : (a,b) \in R\} $$ and $$D_y \subseteq \{b \mid \exists a \in D_x : (a,b) \in R \}$$
Thats fine so far but then there is an example for an instance of a CSP which is not arc consitent: $$ \Bigg( \{x\}, ~~ \{1,2\}, ~~ \bigg\{\Big((x,x),\{(1,1)\}\Big), \Big(x,\{1,2\}\Big)\bigg\} \Bigg)$$
But in my opinion it is arc-consitent because $D_x=\{1\}$ satisfies all the conditions. Am I mistaken?
In addition to that the definition above is not equilvalent to the definition on Wikipedia.
Any ideas?
As Antoine pointed out in his comment $D_x$ is not a set that can be chosen but the domain of the variable $x$. To obtain a arc-consistent instance one has to introduce so called domain constraints which restrict the domain of each variable independently.