Partitioning Problems
3-Dimensional Matching
3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T ⊆ X × Y × Z of triples, does there exist a set of n triples in T such that each element of X ∪ Y ∪ Z is in exactly one of these triples?
Claim. 3-SAT $\leq _p$ 3D-MATCHING
Pf. Given an instance Φ of 3-SAT, we construct an instance of 3D-matching that has a perfect matching iff Φ is satisfiable.
Construction
- Create gadget for each variable x i with 2k core elements and 2k tip elements.
- No other triples will use core elements.
- In gadget i, 3D-matching must use either all the grey triples(corresponding to x i = true) or all the blue ones (corresponding to x i = false).

- For each clause Cj create gadget with two elements and three triples.
- Exactly one of these triples will be used in any 3D-matching.
- Ensures any 3D-matching uses either
-
- grey core of x1
-
- blue core of x2
-
- grey core of x3
-

- There are 2nk tips. nk covered by blue/gray triples, k covered by clause triples.
- To cover the remaining (n-1)k tips, create (n-1)k cleanup gadgets, each connected to all the 2nk tips.

- Q. What are X, Y, and Z? Does each triple contain one element from each of X, Y, Z?
- A. X = red, Y = green, Z = blue
- Pf. =>
- If 3D-matching, then assign xi according to the color of the selected triples in gadget xi
- Pf. <=
- If Φ is satisfiable, then use assignment of xi to select gadget xi triples and use true literal in Cj to select gadget Cj triple

Note
- https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/3dm.pdf
- 每个3-SAT中的变量转换成一个零件,含四个“核心”和四个“边梢”两个部分
- 每一个clause转换为一个含两个“核心”的零件,根据变量取值连接变量零件中的一个“边梢”
- 对每个没有被cover的“边梢”,创建一个“清理零件”去cover掉
3-Colorability
3-COLOR Given an undirected graph G does there exist a way to color the nodes red, green, and blue so that no adjacent nodes have the same color?
Claim. 3-SAT ≤p 3-COLOR
Pf. Given 3-SAT instance Φ, we construct an instance of 3-COLOR that is 3-colorable iff Φ is satisfiable.
Construction.
-
- For each literal, create a node.
-
- Connect each literal to its negation.
-
- Create 3 new nodes T, F, B; connect them in a triangle
-
- Connect each literal to B.
-
- For each clause, add gadget of 6 nodes and 13 edges (to be described later)

Claim. Graph is 3-colorable iff Φ is satisfiable.
Pf. => Suppose graph is 3-colorable.
- Set all the literals with T color to true.
-
- ensures each literal is T or F.
-
- ensures a literal and its negation are opposites.
-
- ensures at least one literal in each clause is T.


Pf. <= Suppose 3-SAT formula Φ is satisfiable
- Color all true literals T.
- Color node below green node F, and node below that B.
- Color remaining middle row nodes B.
- Color remaining bottom nodes T or F as forced.



Note
- 每个变量和它的negation必须是不同的颜色
- 每个节点颜色必须和B不同
- B T F为不同颜色
Numerical Problems
Subset Sum
SUBSET-SUM. Given natural numbers w1, …, wn and an integer W, is there a subset that adds up to exactly W?
Claim. 3-SAT ≤p SUBSET-SUM
Pf. Given an instance Φ of 3-SAT, we construct an instance of SUBSET-SUM hat has solution iff Φ is satisfiable.
Construction. Given 3-SAT instance Φ with n variables and k clauses, form 2n + 2k decimal integers, each of n+k digits, as illustrated below.
- One digit for each variable and for each clause
- Two numbers for each variable
- Two numbers for each clause
- Sum of each variable digit is 1; sum of each clause digit is 4.


Claim. Φ is satisfiable iff there exists a subset that sums to W.
Pf. => Suppose Φ is satisfiable
- Choose numbers corresponding to each true literal
- Since Φ is satisfiable, each clause digit sums to at least 1 from the chosen numbers
- Choose dummy numbers to make each clause digit sum to 4.
Pf. <= Suppose there is a subset that sums to W
- Each variable digit forces the subset to choose exactly one from x and ¬x
- Each clause digit forces the subset to choose at least one literal in the clause
- Assign each variable according to the chosen literal
3D-MATCHING reduces to SUBSET-SUM
Construction. Let X ∪ Y ∪ Z be a instance of 3D-MATCHING with triplet set T. Let n = |X| = |Y| = |Z| and m = |T|.
- Let X = {x1, x2, x3, x4}, Y = {y1, y2, y3, y4} , Z = {z1, z2, z3, z4}
- For each triplet t= ( xi, yj, zk) ∈ T, create an integer wt in base m+1 with 3n digits that has a 1 in positions i, n+j, and 2n+k.
Claim. 3D-matching iff some subset sums to W = 111,…, 111.

Scheduling With Release Times
SCHEDULE-RELEASE-TIMES. Given a set of n jobs with processing time ti, release time ri, and deadline di, is it possible to schedule all jobs on a single machine such that job i is processed with a contiguous slot of ti time units in the interval [ri, di]?
Claim. SUBSET-SUM ≤p SCHEDULE-RELEASE-TIMES.
Pf. Given a instance of SUBSET-SUM w1, …, wn, and target W.
- Create n jobs with processing time ti = wi, release time ri = 0, and deadline $d_i = 1 + \sum_{j} w_j$.
- Create job 0 with t0 = 1, release time r0 = W, and deadline d0 = W+1.

Summary
- Decision problem. Answer yes/no.
- P. Decision problems for which there is a poly-time algorithm.
- NP. Decision problems for which there exists a poly-time certifier.
- Algorithm C(s, t) is a certifier for problem X if for every string s, s ∈ X iff there exists a string t such that C(s, t) = yes.
- co-NP. Complements of decision problems in NP.
- EXP. Decision problems for which there is an exponential-time algorithm.
- Claim. P ⊆ NP, co-NP ⊆ EXP