A consistency notion in constraint programming:

Let $P = (X, D, C)$ be a CSP.

Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is $k$-consistent iff for any $k$th variable $x_{i_{k}} \in X \setminus Y$ there exists a value $v_{i_{k}} \in D(x_{i_{k}})$ such that $I \cap \{ (x_{i_k}, v_{i_k}) \}$ is locally consistent. The CSP $P$ is $k$-consistent iff for any set $Y$ of $k-1$ variables, any locally consistent instantiation on $Y$ is $k$-consistent.

For example, 3-consistency ensures that any instantiation any pair of variables can be extended to an instantiation involving any third variable without violating any constraint. It is equivalent to path consistency. Similarly, 2-consistency is also known as arc consistency.

My question is how convex geometry can ensure global consistency, because it seems that there is a relationship between consistency and convexity. Because Row Convex Constraint with path(3)-consistency guarantees global consistency.

Can any one help me finding a track to research or a way to prove this relationship?

  • 2
    $\begingroup$ This is a very dense question. CSPs aren't my area, so I don't know if this is known result that's hard to understand or an active area of research. But you might unpack some of the jargon here if you want to make the question more approachable. $\endgroup$ – Bill Barth May 25 '14 at 22:54
  • $\begingroup$ I would definitely second Bill's suggestion. $\endgroup$ – Wolfgang Bangerth May 28 '14 at 0:43

Your Answer

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

Browse other questions tagged or ask your own question.