Watched Eric Demaine's lecture and initially did not understand the reduction from 3-SAT to 3-dimensional matching.
- Complexity: P, NP, NP-completeness, Reductions https://youtu.be/eHZifpgyH_4?t=2786
To reduce 3-SAT to 3DM, we need to show how to express every 3-SAT problem as a 3DM problem. If 3DM has a solution, then that solution can be applied to solve any 3-SAT problem.
-
3-SAT: for a given boolean formula that is a conjunction (logical-AND) of 3-term OR clauses; does there exist a boolean vector b that makes the whole formula true?
-
3DM: out of a set T of triplets (x, y, z), x from X, y from Y, z from Z; X, Y, Z disjoint and all of size n; does there exist a subset S (of size n) where each element of X, Y, and Z appears exactly once?
Will need to create three types of gadgets, to represent clauses, variables, and garbage collection.
Consider a clause (number 1):
- Invent two nodes
$y_{c1}$ ,$z_{c1}$ for this clause, and create the triplets:$(b_{i1}, y_{c1}, z_{c1})$ ,$(b_{j1}, y_{c1}, z_{c1})$ ,$(b_{k1}, y_{c1}, z_{c1})$ .
Since these are the only triplets in T with
The variable nodes in each clause also participate in special "wheel" gadgets that are designed to represent the boolean
(true/false) state of each variable. Suppose
- Invent 2n additional nodes:
$y_{i1}$ through$y_{in}$ ,$z_{i1}$ through$z_{in}$ . - Create 2n triplets:
-
$(b_{i1}, y_{i1}, z_{i1})$ ,$(b_{i2}, y_{i2}, z_{i2})$ , ...,$(b_{in}, y_{in,} z_{in})$ -
$(not-b_{i1}, y_{i2}, z_{i1})$ ,$(not-b_{i2}, y_{i3}, z_{i2})$ , ...,$(not-b_{in}, y_{i1}, z_{in})$
-
- Observe:
- Each of the
$y_i$ and$z_i$ nodes appears in exactly two triplets in$T$ : one with a$b_i$ node and one with a not-$b_i$ node - Due to the structure of the wheel, either all of the
$b_i$ triplets are in$S$ , or all the not-$b_i$ triplets are in$S$ . This enforces the boolean quality of the variable. - For this gadget, the triplets in S are the ones that are not used to make the clauses true. This is because the nodes put into S from the clause gadget (which also appear in the variable gadget) are unavailable.
- Each of the
In the above, I've made all the
There will be:
\sum
additional
The simplest 3-SAT formula contains just a single clause with a single variable. Let's express this as a 3DM problem. (The below may be more complicated than it needs to be.)
-
Clause triplets:
$(x_1, y_c, z_c)$ ,$(x_2, y_c, z_c)$ ,$(x_3, y_c, z_c)$ -
Variable triplets:
$(x_1, y_1, z_1)$ ,$(x_2, y_2, z_2)$ ,$(x_3, y_3, z_3)$ ,$(not-x_1, y_2, z_1)$ ,$(not-x_2, y_3, z_2)$ ,$(not-x_3, y_1, z_3)$ -
Garbage triplets:
$(x_1, y_{g1}, z_{g1})$ ,$(x_2, y_{g1}, z_{g1})$ ,$(x_3, y_{g1}, z_{g1})$ ,$(x_1, y_g2, z_g2)$ ,$(x_3, y_g2, z_g2)$ ,$(x_3, y_g2, z_{g2})$ ,$(not-x_1, y_{g1}, z_{g1})$ ,$(not-x2, y_{g1}, z_{g1})$ ,$(not-x_3, y_{g1}, z_{g1})$ ,$(not-x_1, y_{g2}, z_{g2})$ ,$(not-x_3, y_{g2}, z_{g2})$ ,$(not-x_3, y_{g2}, z_{g2})$
T has these 21 triplets; n = 6
One valid subset S consists of:
- (x_1, y_c, z_c),
- (not-x_1, y_2, z_1), (not-x_2, y_3, z_2), (not-x_3, y_1, z_3)
- (x_2, y_g_1, z_g_1), (x_3, y_g_2, z_g_2)
which corresponds to setting x = true.
This is a 3-SAT formula with two clauses and three variables. It's underdetermined, so there could be multiple solutions.
-
Clause triplets:
- (p, y_c_1, z_c_1), (q, y_c_1, z_c_1), (r, y_c_1, z_c_1)
- (not-p, y_c_2, z_c_2), (not-q, y_c_2, z_c_2), (not-r, y_c_2, z_c_2)
-
Variable triplets:
- (p, y_p_1, z_p_1), (not-p, y_p_1, z_p_1)
- (q, y_q_1, z_q_1), (not-q, y_q_1, z_q_1)
- (r, y_r_1, z_r_1), (not-r, y_r_1, z_r_1)
-
Garbage triplets (3 variable triplets minus 2 clauses = 1 garbage):
- (p, y_g_1, z_g_1), (q, y_g_1, z_g_1), (r, y_g_1, z_g_1), (not-p, y_g_1, z_g_1), (not-q, y_g_1, z_g_1), (not-r, y_g_1, z_g_1)
T has 18 triplets; n = 6.
One valid subset S consists of:
- (p, y_c_1, z_c_1), (not-q, y_c_2, z_c_2)
- (not-p, y_p_1, z_p_1), (q, y_q_1, z_q_1), (not-r, y_r_1, z_r_1)
- (r, y_g_1, z_g_1)
which corresponds to p = true, q = false, r = true.