算法设计与分析笔记0x0E —— Part 3 NP完全

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 C_j 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
  • 1. grey core of x₁
  • 2. blue core of x₂
  • 3. grey core of x₃

• 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 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/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.

• 1. For each literal, create a node.
• 2. Connect each literal to its negation.
• 3. Create 3 new nodes T, F, B; connect them in a triangle
• 4. Connect each literal to B.
• 22. 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.
• 4. ensures each literal is T or F.
• 2. ensures a literal and its negation are opposites.
• 22. 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 w₁, …, w_n 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 = {x₁, x₂, x₃, x₄}, Y = {y₁, y₂, y₃, y₄} , Z = {z₁, z₂, z₃, z₄}
• 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. 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 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. SUBSET-SUM ≤_p SCHEDULE-RELEASE-TIMES.
Pf. Given a instance of SUBSET-SUM w₁, …, 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₀ = 1, release time r₀ = W, and deadline d₀ = 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