# Contraint with three variables into three binary constraints

I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint:

$A+B= C$

One is supposed to represent this one constraint using three binary constraints. Is this even possible? No domain is given, but even if it was, I really don't see how this could be achieved...

• Are the examples in Binarization of Constraints useful? – hengxin Jun 14 '15 at 2:25
• Some key data is missing. What type are A,B,C? What is a binary constraint? As it is, the problem is more like a zen koan. – Yuval Filmus Jun 18 '15 at 18:58
• The exercise I found states nothing more about the variables. A binary constraint is a constraint which... constrains two variables. But nevermind this question anymore, I think I more or less understand the binarization process now (even if I don't feel it). – Jules Jun 18 '15 at 19:40

Good question. Your instinctive reaction is quite valid: if you stick with the variables $A,B,C$, there is no way to introduce some set of binary constraints that will be equivalent to $A+B=C$ (where each constraint is only allowed to mention two of $A,B,C$).

The trick is to introduce new variables, or change the set of variables. If you do that, it can be done. For instance, see the reference that hengxin suggests: http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html. However, it would be understandable if you feel that this is in some sense "cheating"... which might be why you didn't think of this approach.

• But this solution (which didn't fully grasp yet) as stated in the article On the Conversion between Non-Binary and Binary Constraint Satisfaction Problems (cs.toronto.edu/~fbacchus/Papers/BvBAAAI98.pdf) applies only if the domain for each variable is finite. Here the domain is R I think. – Jules Jun 14 '15 at 9:20
• @Jules, I believe you can still do the same trick with an infinite domain. The domain of the new variables will also be infinite (as well), but you're already in that situation... – D.W. Jun 14 '15 at 10:21
• I guess I don't get the trick then. All is clear to me until we define new contraints as $X = 1st(U)$ and so on... But $U$ is a set of tuples and X should be a number or a range of numbers, not a tuple, especially if $U=\{(X,Y,Z): SomeConstraint(X,Y,Z)\}$. What am I missing? – Jules Jun 14 '15 at 12:57
• agreed with jules re this answer not being fully clear/ detailed. the ref is helpful but has many examples and its not clear/ clearly stated which one applies, a better answer would at least identify which example is relevant, & better yet relate it directly to the original question. & what interpretation exactly are you using for eqn A + B = C? – vzn Jun 21 '15 at 16:38
• @Jules, you define a new variable $U$ that takes values on $\mathbb{R}^3$. Now, the original constraint $A+B=C$ can be defined as a unary constraint on $U$: namely, $U \subseteq \mathcal{S}$ where the set $\mathcal{S}$ is defined as $\mathcal{S} = \{(r,s,r+s) : r,s \in \mathbb{R}\}$. (That's a unary constraint, because it only involves one variable, namely $U$.) You can also introduce a binary constraint $X=\text{1st}(U)$ (this is a binary constraint, as it involves the two variables $X,U$), etc. In short: The exact same trick works for infinite domains as well, with no significant changes. – D.W. Jun 21 '15 at 22:50

agreed there is not enough info. please clarify. lacking that here is one interpretation; your ref may be using "+" to refer to binary OR ($\vee$), this is common in many refs. then we have the table

a + b = c
0   0   0
0   1   1
1   0   1
1   1   1


leading to a truth table (x is true iff the eqn A + B = C holds)

a b c x
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1


this can be encoded as four binary constraints but not fewer (proof exercise for reader):

$(A \vee B \vee \bar{C}) \wedge (A \vee \bar{B} \vee C) \wedge (\bar{A} \vee B \vee C) \wedge (\bar{A} + \bar{B} + C)$

however introducing auxiliary (free) variable D one can write using 3 boolean constraints:

$(C \vee \bar{D}) \wedge (\bar{A} \vee D) \wedge (\bar{B} \vee D)$

background: this is basically the same construction used in the Tseitin transform (exercise for reader to show the correspondence).

• 1. A binary constraint is one that constrains two variables. $(A \lor B \lor \overline{C})$ is not a binary constraint: it involves three variables, so it is a "trinary" (3-ary) constraint. The arity of a constraint is the number of variables it refers to. 2. The latter formula is not correct. It is not equisatisfiable with the original. For instance, $A=B=D=\text{False}$ and $C=\text{True}$ satisfies your formula but does not satisfy the original formula. In general, the Tseitin transform gives you a formula where some clauses have 3 clauses, so it doesn't give an answer to this question. – D.W. Jun 21 '15 at 22:47
• presumably you mean in your last sentence "some clauses have 3 variables" – vzn Jun 22 '15 at 2:54
• Oops, yes, that was what I meant. Sorry about that. – D.W. Jun 22 '15 at 3:10