4
$\begingroup$

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...

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Are the examples in Binarization of Constraints useful? $\endgroup$ – hengxin Jun 14 '15 at 2:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 18 '15 at 18:58
  • $\begingroup$ 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). $\endgroup$ – Jules Jun 18 '15 at 19:40
3
+50
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jules Jun 14 '15 at 9:20
  • $\begingroup$ @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... $\endgroup$ – D.W.♦ Jun 14 '15 at 10:21
  • $\begingroup$ 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? $\endgroup$ – Jules Jun 14 '15 at 12:57
  • $\begingroup$ 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? $\endgroup$ – vzn Jun 21 '15 at 16:38
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W.♦ Jun 21 '15 at 22:50
-1
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Jun 21 '15 at 22:47
  • $\begingroup$ presumably you mean in your last sentence "some clauses have 3 variables" $\endgroup$ – vzn Jun 22 '15 at 2:54
  • $\begingroup$ Oops, yes, that was what I meant. Sorry about that. $\endgroup$ – D.W.♦ Jun 22 '15 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.