3
$\begingroup$

I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language):

# set up vars & their domains
x_1 {1}
x_2 {0,1}
x_3 {0}
x_4 {0,1}
# constraints
(x_1 != x_2)
(x_2 = x_3)
(x_3 = x_4)
(x_1 != x_4)
(x_2 = x_4)

The objective is then to choose values from the domains of each variable so as to maximize the number of constraints satisfied.

More generally, in all of my instances, we have a fixed value of $k$. The domain of each variable is of size at most $k$. Every constraint involves two variables, and is an inequality or an equality constraint.

When CSPs are studied from a theoretical viewpoint, is there a model that captures the above in a straightforward way?

$\endgroup$
  • $\begingroup$ @AlwynMathew Please stop micro-managing formatting if it does not solve a problem. (Here, it actually made things worse, imho.) $\endgroup$ – Raphael Oct 26 '16 at 22:09
  • $\begingroup$ @Raphael subscripts are not correctly displayed so I was trying to make that proper. $\endgroup$ – Alwyn Mathew Oct 27 '16 at 4:01
  • $\begingroup$ @AlwynMathew I see. The pseudo code is very clear, though, even with pseudo subscripts. $\endgroup$ – Raphael Oct 27 '16 at 9:36
3
$\begingroup$

In complexity theory, CSPs are usually specified as a set of allowed predicates. If the (finite) domain is $D$, a predicate of arity $d$ is an arbitrary subset of $D^d$ of allowed values. In particular, equality (or inequality) is a predicate of arity 2.

This is the point of view taken in Schaefer's dichotomy theorem as well as the more recent universal algebra approach (see for example a short survey by Libor Barto). Another example is the celebrated Raghavendra's theorem, which states that assuming the unique games conjecture, every CSP can be approximated optimally using semidefinite programming.

$\endgroup$

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.