Re: HW3 Ques 1

[Subbarao Kambhampati <rao@asu.edu>]

At 11:19 PM 10/4/2001 -0700, you wrote:
>Hi Rao,
>
>   In HW2, problem 5, there are two constraints that have are between three
>constraints. They are namely C2: "J2 has to be done either before j3 or
>before j4" and C3: "Job j3 cannot be done on the same day as job j2 or job
>j4." But in question 1 HW3, you only fix C2 to be binary, but not C3. Does
>that still leave this CSP problem non-binary? If so, how can we draw the
>constraint graph for the problem? Is there something I'm understanding
>incorrectly?? Thanks in advance.
>
>Luis

THe constraint C3, while 3-ary on the surface, is really a conjunction of 2 
2-ary constraints:
J3 cannot be done on the same day as J2  & J3 cannot be done on same day as J4

In general when we talk about an n-ary constraint, we mean one which 
ccannot be trivially converted into a set of k-ary constraints with k<<n. 
(I say trivially converted since if you are allwed to introduce new 
variables correspondings to subsets of old variables, then any
n-ary constraint can ultimately be converted down to k-ary constraints k<<n)

Rao