1
$\begingroup$

I am trying to develop a reduction from the 3-Dimensional Matching graph problem to the Boolean Satisfiability problem. The task is a tad odd because usually the direction of the reduction is in reverse, with SAT\3-SAT being reduced to some other problem in order to demonstrate that the target is NP-hard. Nevertheless, both are NP-complete so the reduction must exist.

For 3-D Matching, there are n3 possible, distinct triples formed from the Cartesian-Product of the 3 disjoint sets (sometimes refereed to as "genders" when related to the marriage problem). Each element/item in the Union of the disjoint sets will appear in n2 of the distinct triples; moreover, every item from a disjoint set will "pair-up" n times with an arbitrary item from another disjoint set. Items from the same disjoint set never appear in the same triple. This much I can see.

I have chosen to express potential, distinct triples as Boolean literals (a Boolean variable and its negation) in the SAT expression. "Gender" set elements are also expressed as Boolean literals. When a triple is chosen (made TRUE), the Boolean SAT expression should be formulated to forbid choosing (setting TRUE) any other triple containing the same combination of elements [e.g. (A, B, C) forbids {(A, D, F), (A, B, G), etc...}]. Exclusive OR (XOR) nicely expresses this restriction but only for two elements. It breaks down for n elements.

I know how to express what I want in English:

--------------From the subset of triples containing an arbitrarily chosen element, [there are n2 such triples] you must choose exactly 1 triple; all other triples are invalidated.

I have no idea how to express this in Boolean terms. Is there such an "Exclusive OR" for a set of n elements? Clearly, Boolean expression exists for other requirements which can be expressed in English:

  1. You must take all element --> Conjunction over all Boolean variables
  2. You must not take any element --> Conjunction over all the complement (negation) of Boolean variables
  3. You must take at least one element --> Disjunction over all Boolean Variables
  4. You must exclude at least one element --> Disjunction over all the complement of Boolean variables

It would seem to me that the Boolean analog to such common Word problems, such as "you must take exactly one", would be cataloged somewhere but I have not found it in my search. Can anyone set me on the right track. Thank You.

P.S. the answer to the reduction supposedly rests here but I really don't understand the solution. I would like to be able to prove their formulation to myself through propositional logic. https://www2.cs.duke.edu/courses/summer11/cps130/files/hw6-answers.pdf

$\endgroup$
3
$\begingroup$

If $x_i$ are literals for $i\in\{1,\dots,n\}$, "exactly one true" is equivalent to "at least one true" and "no pair has both true": $$\left(\bigvee_{i=1}^n x_i\right) \land \left(\neg \bigvee_{1 \le i<j \le n} (x_i \land x_j)\right)$$ Equivalently, $$\left(\bigvee_{i=1}^n x_i\right) \land \left(\bigwedge_{1 \le i<j \le n} (\neg x_i \lor \neg x_j)\right)$$

$\endgroup$
3
  • $\begingroup$ Thank You so much! I was so stuck thinking about things from Conjunctive Normal Form that I didn't think to describe clauses with AND operators inside. Does the bottom Transformation come from DeMorgan's Laws? $\endgroup$ – H3G3moKnight Mar 18 '20 at 7:49
  • $\begingroup$ Yes, DeMorgan’s Laws. $\endgroup$ – RobPratt Mar 18 '20 at 12:28
  • $\begingroup$ @RobPratt do you know any similar concise way to express: exactly n true? $\endgroup$ – Al Bundy Jun 4 '20 at 12:41

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.