Reducing 3-SAT to 3-dimensional matching

np-completeness-reduce-3sat-to-3dm.md

Watched Eric Demaine's lecture and initially did not understand the reduction from 3-SAT to 3-dimensional matching.

16. Complexity: P, NP, NP-completeness, Reductions https://youtu.be/eHZifpgyH_4?t=2786

Goal

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?

Gadgets

Will need to create three types of gadgets, to represent clauses, variables, and garbage collection.

Clause

Consider a clause (number 1): b_i_1 || b_j_1 || b_k_1

• Invent two nodes y_c_1, z_c_1 for this clause, and create the triplets: (b_i_1, y_c_1, z_c_1), (b_j_1, y_c_1, z_c_1), (b_k_1, y_c_1, z_c_1).

Since these are the only triplets in T with y_c_1, z_c_1 nodes, exactly one of these three triplets must be in S. The selected triplet represents the variable b whose value made this clause true.

Variable

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 b_i and not-b_i appear n times in the clauses.

1. Invent 2n additional nodes: y_i_1 through y_i_n, z_i_1 through z_i_n.
2. Create 2n triplets:
   • (b_i_1, y_i_1, z_i_1), (b_i_2, y_i_2, z_i_2), ..., (b_i_n, y_i_n, z_i_n)
   • (not-b_i_1, y_i_2, z_i_1), (not-b_i_2, y_i_3, z_i_2), ..., (not-b_i_n, y_i_1, z_i_n)
3. 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.

Garbage collection

In the above, I've made all the b_i and not-b_i nodes come from the X set, and generated additional y_i, z_i nodes from the Y and Z sets. We may need to generate extra garbage-collection nodes to pair off the unused wheel nodes.

There will be:

\sum n_i - number of clauses

additional y and z nodes to match with the extra b-variable nodes.

Examples

x || x || x

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_g_1, z_g_1), (x_2, y_g_1, z_g_1), (x_3, y_g_1, z_g_1), (x_1, y_g_2, z_g_2), (x_3, y_g_2, z_g_2), (x_3, y_g_2, z_g_2), (not-x_1, y_g_1, z_g_1), (not-x_2, y_g_1, z_g_1), (not-x_3, y_g_1, z_g_1), (not-x_1, y_g_2, z_g_2), (not-x_3, y_g_2, z_g_2), (not-x_3, y_g_2, z_g_2)

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.

(p || q || r) && (not p || not q || not r)

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.