On the "infinite domain CSP" with codesignation/non-codesignation constraints

[Subbarao Kambhampati <rao@asu.edu>]

Folks

 Sorry for the digression into the finite domain CSP and planning; not only was it an avoidable digression but 

I didn't quite get to the explanation of the punch line before shifting back to the main topic. :-( 

Here is the explanation.

Recall that we are considering a CSP with set of variables X1...Xn, and the only constraints are codesignation (saying Xi must have the same value as Xj)

and non-codesignation Xk must not have the same value as Xj.

If X1...Xn have finite (discrete) domains, clearly this is a normal CSP, and in the worst case can take exponential time to solve.

If on the other hand if X1..Xn all have infinite domains, then the CSP can be solved in polynomial time. Just find the transitive closure on the codesignation constraints

(If X codesignates with Y and Y codesignates with Z then X codesignates with Z.).  Then see if there are any pair of variables X and Y such that they have both codesignation and non-codesignation constraints

between them. If so, the CSP has no solution. Otherwise, it has. 

The reason this trick doesn't work for finite domain CSPs is that a set of non-codesignation constraints can *imply* a codesignation (if X has domain a, b and c, then 

X!=a and X!=b implies X=c); such a thing won't happen in infinite domain case since there are always other values that X can take. 

Rao