7
$\begingroup$

Are programs written in the constraint programming (CP) paradigm more expressive than problems defined as constraint satisfaction problem (CSP)?

Wikipedia says about Constraint_programming:

Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints.

and later:

The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. "A or B is true"), those solved by the simplex algorithm (e.g. "x <= 5"), and others.

If I understand that correctly CPs can describe superset of problems which can be described by CSP.

I'm especially interested in these programs of puzzle solvers written using CP. In the paper they wrote that some rules can not be described using CP so they used something which looks like imperative paradigm. If I cut off imperative part of programs is that valid CSP problem definition?

$\endgroup$
6
$\begingroup$

First of all, I cannot help but point out a practice I consider bad in the way you defined your question. You are comparing a class of algorithms with a class of problems. Although closely related, they are not the same. As an example, consider the halting problem. It is a very well defined problem. However, we know that no Turing Machine can diagnose it. Given the Church-Turing thesis, this is the same as saying that there is no algorithm for this problem.

However, one can rephrase the question such that the items compared are of the same nature. Consider constraint programming (CP) as the computational model A and boolean formulas as the computational model B. I chose boolean formulas because SAT is probably the most known CSP and furthermore boolean formulas have a nice property, which I will use below.

Although I have programmed in Prolog, I cannot say I have a good knowledge of constraint programming. However, I am almost certain that they are Turing-complete. Since they use constraints, one could use them to "simulate" head moves,e.g. if [constraint] then move to this cell . Furthermore, one could write contents into that tape. Therefore, constraint programming is as powerful as Turing Machines. Since all programs in CP are algorithms, they can be simulated by a universal TM. Thus CP and TM have the same expressibility.

One might think at this point that CP is a stronger model that boolean formulas. However, in Arora and Barak's book "Computational Complexity:A Modern Approach", in chapter 2, a proof is given that any boolean function has an equivalent boolean formula ( the theorem is labeled "Universality" of AND,OR and NOT). On a given input, the formula is satisfied if and only if the boolean function is true for this input. As an informal proof, consider that those 3 operators can express any piece of hardware. Furthermore, every other input can be translated into a boolean one. Therefore, every TM can be simulated as a boolean formula. Thus boolean formulas are Turing-complete. Furthermore, there is a TM that can diagnose the satisfiability of a boolean formula. Therefore, boolean formulas and TMs are equivalent.

It follows that the two models have the same expressibility.

$\endgroup$
5
$\begingroup$

As far as I know, constraint programming is traditionally (1) a name of the paradigm for stating problems in terms of variables and constraints between the variables; and thus (2) a well-accepted name of a research area.

(The most resent textbook on the subject is the Handbook of Constraint Programming by Francesca Rossi, Peter van Beek and Toby Walsh, Elsevier, 2006. The first chapter is available online here, where this point is somewhat discussed.)

CSP (i.e. Constraint Satisfaction Problem) is usually a formal definition of the problem; that is, stating what the variables are, the domains of the variables (e.g. bounded, unbounded, discrete, continuous), and the constraints and their representation (e.g. truth tables, propagators).

However, CSP is also used in the same meaning as constraint 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.