+1 vote
1.3k views
in Artificial Intelligence by
Show how a single ternary constraint such as “A + B = C” can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains. (Hint: Consider a new variable that takes on values that are pairs of other values, and consider constraints such as “X is the first element of the pair Y .”) Next, show how constraints with more than three variables can be treated similarly. Finally, show how unary constraints can be eliminated by altering the domains of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.

1 Answer

+2 votes
by
selected by (user.guest)
 
Best answer
The ternary constraint is A + B = C, now to express the ternary constraint in binary, introduce a new variable AB. The domain of AB is the set of pairs of numbers from N, where N is the set of numbers.

The three binary constraints to express the ternary constraint to binary are as follows:

• One constraint is between A and AB according to which the value of A must be equal to the first element of the pair-value value of AB.

• Another constraint is between B and AB, according to which the value of B must be equal to second element of value of AB.

• The sum of the pair of numbers, which means the value of AB must be equal to the value of C.

The process of induction can be used to reduce the ternary constraint to binary constraints. Suppose, there is an n-ary constraint, then this constraint can be reduced to (n – 1) ary constraints through induction. Here, the 3-ary constraint is reduced to binary by reducing the variables A, B, C to binary constraints and then the variable D is added.

Related questions

Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that

ONE SOLUTION

...