Isn't Domain of a variable nothing but a constraint?

Question

In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are saying that this variable can take all these values. Is there any particular reason why domain is defined as a different concept than constraints?

Answer 1

As you observe, restricting the domain of a variable has exactly the same effect as applying a unary constraint to it.

One situation where you might prefer to use unary constraints rather than restricted domains is when you want to control very tightly the relations that are allowed to be used in constraints. For example, if you want to investigate the computational complexity of CSP with a particular class of constraint languages. On the other hand, such investigations often assume that all unary relations are included in the constraint language, which is equivalent to fixing a global domain but allowing the domain of any variable to be any subset of that. (This is known as the "conservative" case because of certain algebraic properties of the constraint langauges.)

Answer 2

Even though a domain may be considered just another type of constraint, there do exist good reasons to keep them separated, and it may be easier to think of them from a pure mathematical standpoint. Domains should in a sense be seen as the definition of the variable in terms of Type - e.g. Integer or Real etcetera. The domains can also be seen as the Master bounds. Defining the domain type (Integer / Real) is also important to help the constraint solver determine what solving method to use for each specific constraint.

I would like to illustrate it with the following example;

Consider the following constraint problem for Pythagoras theorem.

Variables: a b c

Domains: a [1..10] Integer b [1..10] Integer c [1..10] Integer

Constraint: a x a + b x b = c x c

We actually have three unknowns but the finite sets of the domains will allow the constraint solver to find the following solutions for a,b,c;

a = 3,4,6,8 b = 3,4,6,8 c = 5,10

Now let us change the domains from Integer to Real, to the following;

a [1..10] Real b [1..10] Real c [1..10] Real

Simply by changing the domains, it will no longer be possible to find all solutions as there do exist an infinite number of solutions.

Therefore, the domains should in general be seen as the main definition of the total search space (in terms of type and bounds) while the constraints should be seen as the definition of the problem.

Answer 3

I suppose what is called domain for constraint programming corresponds to what would be called type in most contexts, and particularly in most programming languages.

The issue of types is an old one, and I am unfortunately not knowledgeable enough to give you a precise account. But this may hopefully serve as an introduction.

The idea of theorizing types is attributed to Bertrand Russell, to serve as an alternative to set theory and do away with some paradoxes of naive set theory.

What it says, intuitively, is that terms are always supposed to be typed and that operators or predicate make sense only when applied to the proper types. The idea is quite close to static type checking in programming languages. But I suggest you read at least the beginning of the wilipedia page on Type Theory, which seems rather clear.

Thus, as a first approximation, it seems quite possible to do as suggested in the question: consider the domains as simple constraints, on a universal sets of values. That is just returning to naive set theory and its paradoxes, which was however sufficient to do a lot of good mathematics for some time.

But it seems that a cleaner way to do things is to separate values into domains were operations and predicates have meaning. Otherwise, is the value true odd or even, and what is its square root? This is the way to ensure that the language you use (whether constraints or other) will have properly defined semantics, relying hopefully on a consistent logic.

But can we have both consistency and domains as constraints, and is there a cost?

The benefits of typing may come at the cost of Turing Completeness. For example, while (untyped) $\lambda$-calculus is Turing complete, simply typed $\lambda$-calculus is more restricted. Whether typing can be consistent with Turing Completeness is an issue I would not address at my competence level.

An important point of all this however is that typing systems have been shown to be isomorphic to logical predicates, through what is known as the Curry-Howard isomorphism. So this would vindicate from a theoretical perspective the view that domains can be seen as a constraint expressed by some predicate to be satisfied. From this point of view, there is no difference between a formula (to be satisfied) and a type, given appropriate formalization apparatus with a consistent logic.

However, it may be (I do not know) that distinguishing domains from other predicates may be a way of enforcing consistency of the underlying logical system (to be checked).

Now, if you wish for more details, it would be best to asked a full-fledged type theorist, as I am getting onto grounds for which I have no chart.

From a more mundane point of view, you may consider that expressing constraints makes sense only with respect to some domain, and there is in practice a hierarchical structures that enforces the existence of some sense (semantics) to what can be written, and also allows for more efficient implementations. That is pretty much, I believe, why static types were introduced in programming languages, as they had to refer to the encoding techniques used for the corresponding values (though I would not underestimate the influence of logicians on early programming language design, especially Lisp and Algol, that were both extremely influencial).

Of course, if the kind of domains you are willing to consider in your constraint programming language is very restricted, you are probably safe from paradoxes, and could, if you wish, freely see domains as unary constraints as already suggested by David Richerby's answer.