Answers.Body: <p>Let <span class="math-container">$D_a$</span> be the domain for A, and <span class="math-container">$a_i$</span> the elements of <span class="math-container">$D_a$</span>.  Let <span class="math-container">$D_b$</span> and <span class="math-container">$D_c$</span> work similarly for <span class="math-container">$B$</span> and <span class="math-container">$C$</span> respectively.</p>
  
  <p>We introduce <span class="math-container">$D_t = \{t | t = (c_i - b_j, c_i)\}$</span> for all <span class="math-container">$c_i$</span> in <span class="math-container">$D_c$</span> and <span class="math-container">$b_j$</span> in <span class="math-container">$D_b$</span>.  We can see that <span class="math-container">$\{t[0]\}$</span> (i.e. <span class="math-container">$\{c_i - b_j, \forall i,j\}$</span>) must be equal to <span class="math-container">$D_a$</span>.</p>
  
  <p>So we can represent the constraint on <span class="math-container">$A$</span> by the relation <span class="math-container">$R_At = { (a_k, t_l) | a_k = t_l[0]}$</span> for <span class="math-container">$a_k$</span> in <span class="math-container">$D_a$</span> and <span class="math-container">$t_l$</span> in <span class="math-container">$D_t$</span>.  That is, <span class="math-container">$a_k$</span> must equal the first element in the pair from <span class="math-container">$t_l$</span>, which means there is a <span class="math-container">$b_j$</span> and a <span class="math-container">$c_i$</span> consistent with that <span class="math-container">$a_k$</span>.</p>
  
  <p>The constraint on <span class="math-container">$B$</span> is the relation <span class="math-container">$R_{Bt} = \{(b_j, t_l) | b_j + t_l[0] = t_l[1]\}$</span>.  Since <span class="math-container">$t_l$</span>[0] = <span class="math-container">$c_i - b_j$</span>, <span class="math-container">$t_l$</span>[0] + <span class="math-container">$b_j$</span> must equal <span class="math-container">$c_i$</span>, which is t[1], so if this holds, there is a <span class="math-container">$b_j$</span> in <span class="math-container">$D_b$</span> that is consistent with <span class="math-container">$t_l$</span>.</p>
  
  <p>Lastly, <span class="math-container">$R_{Ct} = \{ (c_i, t_l) | c_i = t_l[1]\}$</span>, which is really just an identity.  So what we've done is solved <span class="math-container">$A + B = C$</span> for <span class="math-container">$A$</span> and encoded that into <span class="math-container">$R_{At}$</span>.  From that solution and knowledge of the original <span class="math-container">$C$</span> (stored in t[1]) we can re-create <span class="math-container">$C$</span> from a valid <span class="math-container">$B$</span>, which is the <span class="math-container">$R_{Bt}$</span> relation.</p>
  
  <p>And lastly <span class="math-container">$C$</span> must be in the original set of <span class="math-container">$C$</span>'s used to build all the <span class="math-container">$t$</span>'s.  If all three of these constraints hold, then we must have a <span class="math-container">$C$</span>, a <span class="math-container">$B$</span> used to solve for <span class="math-container">$A$</span>, and an <span class="math-container">$A$</span> that matches that solution.  </p>
  
  <p>The second part is really just path-consistency.  For every <span class="math-container">$A$</span>, choose a <span class="math-container">$B$</span>, and see if there's a possible <span class="math-container">$C = A + B$</span>.  If so, Add that those values to final domains <span class="math-container">$D_a$</span>, <span class="math-container">$D_b$</span>, and <span class="math-container">$D_c$</span>.  I forget if there's a better performing algorithm than this, but I doubt it since here you can use associativity of addition to avoid checking the opposite order of selecting <span class="math-container">$A$</span> and <span class="math-container">$B$</span>.  In general, you have to consider both orders.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-09T15:54:50.593Z
Answers.Text: Slightly more informally: Instead of one sum relation C = A + B, we introduce 3 relations:
  
  FirstOfPair(A,D)
  SecondOfPair(B,D)
  SumOfPair(C,D)
  Domain of D is 2-dimensional equivalent of the domains of A, B, C.
Answers.UserDisplayName: Amrinder Arora
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-03-27T00:43:30.033Z
Answers.LastActivityDate: 2018-10-09T01:51:23.317Z
Answers.LastEditDate: 2018-10-09T01:51:23.317Z
Answers.UserDisplayName: jspencer
Body: <p>I'm trying to solve problem 6.6 from the book <em><a href="https://en.wikipedia.org/wiki/Artificial_Intelligence:_A_Modern_Approach" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach</a></em>, by Peter Norvig and Stuart Russell.</p>
  <p>This is in the context of <a href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel="nofollow noreferrer">Constraint Satisfaction Problem</a> and how you can re-formulate some problems with the constraints expressed as a bunch of binary constraints to use the generalized solver CSP algorithm.</p>
  <p>But I'm stuck with that exercise, I can't sketch a demonstration.</p>
  <blockquote>
  <p>6.6  Show how a single ternary constraint such as &quot;A + B = C&quot; can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains.</p>
  <p>(Hint: Consider a new variable that takes on values that are pairs of others values, and consider constraints such as &quot;X is the first element of the pair Y.&quot;) Next, show how constraints can be eliminated by altering the domain of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.</p>
  </blockquote>
  
Tags: <ai-design><constraint-satisfaction-problems><norvig-russell>
Title: How to turn a ternary constraint into three binary constraints?
UserDisplayName: Cristóbal Alcázar
ThreadText: # How to turn a ternary constraint into three binary constraints?
  
  (Asked by: username_0 on 2017-10-31)
  
  I'm trying to solve problem 6.6 from the book *[Artificial Intelligence: A Modern Approach](https://en.wikipedia.org/wiki/Artificial_Intelligence:_A_Modern_Approach)*, by Peter Norvig and Stuart Russell.
  
  This is in the context of [Constraint Satisfaction Problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem) and how you can re-formulate some problems with the constraints expressed as a bunch of binary constraints to use the generalized solver CSP algorithm.
  
  But I'm stuck with that exercise, I can't sketch a demonstration.
  
  > 6.6 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 others values, and consider constraints such as "X is the first element of the pair Y.") Next, show how constraints can be eliminated by altering the domain of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.
  
  **Tags:** ai-design, constraint-satisfaction-problems, norvig-russell
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-03-27. Score: 8 | Accepted answer
  
  Let $D\_a$ be the domain for A, and $a\_i$ the elements of $D\_a$. Let $D\_b$ and $D\_c$ work similarly for $B$ and $C$ respectively.
  
  We introduce $D\_t = \{t | t = (c\_i - b\_j, c\_i)\}$ for all $c\_i$ in $D\_c$ and $b\_j$ in $D\_b$. We can see that $\{t[0]\}$ (i.e. $\{c\_i - b\_j, \forall i,j\}$) must be equal to $D\_a$.
  
  So we can represent the constraint on $A$ by the relation $R\_At = { (a\_k, t\_l) | a\_k = t\_l[0]}$ for $a\_k$ in $D\_a$ and $t\_l$ in $D\_t$. That is, $a\_k$ must equal the first element in the pair from $t\_l$, which means there is a $b\_j$ and a $c\_i$ consistent with that $a\_k$.
  
  The constraint on $B$ is the relation $R\_{Bt} = \{(b\_j, t\_l) | b\_j + t\_l[0] = t\_l[1]\}$. Since $t\_l$[0] = $c\_i - b\_j$, $t\_l$[0] + $b\_j$ must equal $c\_i$, which is t[1], so if this holds, there is a $b\_j$ in $D\_b$ that is consistent with $t\_l$.
  
  Lastly, $R\_{Ct} = \{ (c\_i, t\_l) | c\_i = t\_l[1]\}$, which is really just an identity. So what we've done is solved $A + B = C$ for $A$ and encoded that into $R\_{At}$. From that solution and knowledge of the original $C$ (stored in t[1]) we can re-create $C$ from a valid $B$, which is the $R\_{Bt}$ relation.
  
  And lastly $C$ must be in the original set of $C$'s used to build all the $t$'s. If all three of these constraints hold, then we must have a $C$, a $B$ used to solve for $A$, and an $A$ that matches that solution.
  
  The second part is really just path-consistency. For every $A$, choose a $B$, and see if there's a possible $C = A + B$. If so, Add that those values to final domains $D\_a$, $D\_b$, and $D\_c$. I forget if there's a better performing algorithm than this, but I doubt it since here you can use associativity of addition to avoid checking the opposite order of selecting $A$ and $B$. In general, you have to consider both orders.
  
  > **Comments:**
  > **username_2**: Slightly more informally: Instead of one sum relation C = A + B, we introduce 3 relations:  FirstOfPair(A,D) SecondOfPair(B,D) SumOfPair(C,D) Domain of D is 2-dimensional equivalent of the domains of A, B, C.  
  
  ---
  
  