算法设计与分析笔记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 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
      1. grey core of x1
      1. blue core of x2
      1. 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.

    1. For each literal, create a node.
    1. Connect each literal to its negation.
    1. Create 3 new nodes T, F, B; connect them in a triangle
    1. Connect each literal to B.
    1. 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.
    1. ensures each literal is T or F.
    1. ensures a literal and its negation are opposites.
    1. 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

Leave a Reply

Your email address will not be published.