Partitioning Problems
3Dimensional Matching
3DMATCHING. 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?
3DMATCHING. 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. 3SAT $\leq _p$ 3DMATCHING
Pf. Given an instance Φ of 3SAT, we construct an instance of 3Dmatching 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, 3Dmatching 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 C_{j} create gadget with two elements and three triples.
 Exactly one of these triples will be used in any 3Dmatching.
 Ensures any 3Dmatching uses either

 grey core of x_{1}

 blue core of x_{2}

 grey core of x_{3}

 There are 2nk tips. nk covered by blue/gray triples, k covered by clause triples.
 To cover the remaining (n1)k tips, create (n1)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 3Dmatching, then assign x_{i} according to the color of the selected triples in gadget x_{i}
 Pf. <=
 If Φ is satisfiable, then use assignment of x_{i} to select gadget x_{i} triples and use true literal in C_{j} to select gadget C_{j} triple
Note
 https://www.cs.cmu.edu/~ckingsf/bioinfolectures/3dm.pdf
 每个3SAT中的变量转换成一个零件，含四个“核心”和四个“边梢”两个部分
 每一个clause转换为一个含两个“核心”的零件，根据变量取值连接变量零件中的一个“边梢”
 对每个没有被cover的“边梢”，创建一个“清理零件”去cover掉
3Colorability
3COLOR 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. 3SAT ≤_{p} 3COLOR
Pf. Given 3SAT instance Φ, we construct an instance of 3COLOR that is 3colorable 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 3colorable iff Φ is satisfiable.
Pf. => Suppose graph is 3colorable.
 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 3SAT 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
SUBSETSUM. Given natural numbers w_{1}, …, w_{n} and an integer W, is there a subset that adds up to exactly W?
Claim. 3SAT ≤_{p} SUBSETSUM
Pf. Given an instance Φ of 3SAT, we construct an instance of SUBSETSUM hat has solution iff Φ is satisfiable.
Construction. Given 3SAT 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
3DMATCHING reduces to SUBSETSUM
Construction. Let X ∪ Y ∪ Z be a instance of 3DMATCHING with triplet set T. Let n = X = Y = Z and m = T.
 Let X = {x_{1}, x_{2}, x_{3}, x_{4}}, Y = {y_{1}, y_{2}, y_{3}, y_{4}} , Z = {z_{1}, z_{2}, z_{3}, z_{4}}
 For each triplet t= ( x_{i}, y_{j}, z_{k}) ∈ T, create an integer w_{t} in base m+1 with 3n digits that has a 1 in positions i, n+j, and 2n+k.
Claim. 3Dmatching iff some subset sums to W = 111,…, 111.
Scheduling With Release Times
SCHEDULERELEASETIMES. Given a set of n jobs with processing time t_{i}, release time r_{i}, and deadline d_{i}, is it possible to schedule all jobs on a single machine such that job i is processed with a contiguous slot of t_{i} time units in the interval [r_{i}, d_{i}]?
Claim. SUBSETSUM ≤_{p} SCHEDULERELEASETIMES.
Pf. Given a instance of SUBSETSUM w_{1}, …, w_{n}, and target W.
 Create n jobs with processing time t_{i} = w_{i}, release time r_{i} = 0, and deadline $d_i = 1 + \sum_{j} w_j$.
 Create job 0 with t_{0} = 1, release time r_{0} = W, and deadline d_{0} = W+1.
Summary
 Decision problem. Answer yes/no.
 P. Decision problems for which there is a polytime algorithm.
 NP. Decision problems for which there exists a polytime 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.
 coNP. Complements of decision problems in NP.
 EXP. Decision problems for which there is an exponentialtime algorithm.
 Claim. P ⊆ NP, coNP ⊆ EXP