<p>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. </p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Turing_completeness">Turing-complete</a>. 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.</p>

<p>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.</p>

<p>It follows that the two models have the same expressibility.</p>

CC BY-SA 2.5
2010-12-10T00:59:20.373Z
2010-12-10T00:59:20.373Z
chazisop
<p>As far as I know, <b>constraint programming</b> 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.</p>

<p>(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 <a href="http://www.math.unipd.it/~frossi/chapter4.pdf" rel="noreferrer">here</a>, where this point is somewhat discussed.) </p>

<p><b>CSP</b> (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). </p>

<p>However, <b>CSP</b> is also used in the same meaning as <b>constraint programming</b>.</p>

CC BY-SA 2.5
2010-12-09T09:20:27.000Z
2010-12-09T09:20:27.000Z
Standa Zivny
<p>Are programs written in the <a href="http://en.wikipedia.org/wiki/Constraint_programming">constraint programming</a> (CP) paradigm more expressive than problems defined as <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem">constraint satisfaction problem</a> (CSP)?</p>

<p>Wikipedia says about Constraint_programming: </p>

<blockquote>
  <p>Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints.</p>
</blockquote>

<p>and later:</p>

<blockquote>
  <p>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 &lt;= 5"), and others.</p>
</blockquote>

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

<p>I'm especially interested in <a href="http://krr.sabanciuniv.edu/projects/gridpuzzleASPvsCP/">these programs of puzzle solvers</a> 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?</p>

<ds.algorithms><csp>
What relation is between constraint satisfaction problems and constraint programming?
Scrool
# What relation is between constraint satisfaction problems and constraint programming?

(Asked by: username_0 on 2010-12-09)

Are programs written in the [constraint programming](http://en.wikipedia.org/wiki/Constraint_programming) (CP) paradigm more expressive than problems defined as [constraint satisfaction problem](http://en.wikipedia.org/wiki/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](http://krr.sabanciuniv.edu/projects/gridpuzzleASPvsCP/) 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?

**Tags:** ds.algorithms, csp

---

## 2 answers

### Answer by username_1 on 2010-12-10. Score: 7 | Accepted answer

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](http://en.wikipedia.org/wiki/Turing_completeness). 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.


---

### Answer by username_2 on 2010-12-09. Score: 5

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](http://www.math.unipd.it/~frossi/chapter4.pdf), 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**.


---

