5 Structural Complexity: NPc Comparing Problems: polynomial-time reduction Reductions: CLIQUE p IS p SAT p 3SAT p IS NP-completeness, Master Reduction coNP, Ladner's Theorem CS422 M. Ziegler Comparing Problems, again CS422 M. Ziegler CLIQUE = { G,k | G contains a k-clique } p IS={ G,k : G has k pairwise non-connected vertices} f L LC L' L'C For L,L' write L p L' if exists a polynomial-time computable f: such that x: xL f(x)L'. a)
a) L' L' decidable P LP so L. b) L p L' p L'' L p L' Reduction IS p SAT CS422 M. Ziegler Goal: Upon input of (the encoding of) a graph G and k, produce in polynomial time a CNF formula such that: satisfiable iff G contains k independent vertices Let G consist of vertices V={1,..,n} and edges E. Consider Boolean variables xv,i, v V, i=1...k There is an i-th vertex Vertex v is #i among the k independent. and clauses Ki := vV
xv,i, i=1...k and xv,i xv,j, v V, 1i
Introduce new variables u,v, and consider ' := ( a b u ) (u c d ) f: ' ( p q v) (v r s ) For L,L' write L L' if exists a computable f: such that x: xL f(x)L'. Reduction 3SAT p IS CS422 M. Ziegler Produce, given a 3-CNF term , within polynomial time a graph G and integer k such that it holds: is satisfiable iff G contains k pairwise non-adjacent vertices. e.g. ( u .... ) ( .. u .. ) ( .. .. u ) ( u .. .. ) = C1 C2 Ck, Ci = xi1 xi2 xi3, xis literals V:= { (i,1),(i,3): ik }, E:= { {(i,s),(j,t)} : i=j or xis= xjt } (k,1) (1,1) (k,2) (1,2)
(1,3) Richard Karp (k,3) Problems of similar complexity CS422 M. Ziegler unknown yet Showed: CLIQUE p IS p SAT p 3SAT p IS. These 4 problem have about same complexity: Either all are belong to P, or none of them. We will show: Also TSP, HC, VC and many further problems in NP belong to this class called NPc. And will show: These are hardest problems in NP. CookLevin Theorem: L 2 NP : L p SAT. That is, either all or none of the problems in NPc can be decided in polynomial time. In the first case: A deterministic WHILE+ program could simulate any non-deterministic one with polynomial slowdown! Complexity Class Picture Def: ANP is NP-complete if L p A holds for every LNP.
Theorem (Cook'72/Levin'71): SAT is NP-complete! Lemma: For A NP-complete and A p B NP, B is also NPc. Now know 500 natural problems NP-complete EXP CS422 M. Ziegler PSPACE complete PSPACE CH #P PH PNP NPcomplete coNPcomplete coNP
NP P Scenarios for PNP coNP := { L : \L NP } CS422 M. Ziegler unSAT := { Boolean term, x: (x)=0 } coNPc Theorem [Ladner'75]: If PNP, NP there exists LNP \ (PNPc) NPc NP = coNP P= coP NP c c P N o c
NP NP coNP NP coNP P coNP P= coP Master Reductions SAT = { : Boolean term, y ,y : (y ,y )=1} CS422 M. Ziegler 1 m 1 m Cook/Levin Theorem: SAT is NP-complete! Proof (Sketch): Fix LNP and VP. Fix WHILE+ program B deciding V in time poly(n).
Express "bin(z0,zk-1)V" x := n+k(bin(x), ) as Boolean term "k(z0,zk-1)=1" of length poly(k). Then bin(x0,xn-1)L y0,ym-1{0,1}: n+k(x, y)=1. Thm: The following problem UNP is NP-complete: { A,x,2N : nondetermin. WHILE+ program A accepts input x within at most N steps } L = {x: y, (y)poly((x)), x,yV }, VP SubsetSum is NP-complete CS422 M. Ziegler { a1,aN,b | a1,aN,b, 1,N{0,1} : b=i aii } SubsetSumNP Show: 3SAT p SubsetSum In polyn.time: 3CNF A and b s.t. satisf. assignm. of BA: b=aB a Eg. = (x1 x3 x5) (x1 x5 x4) (x2 x2 x5) v1 := 100 10000 v2 := 000 01000 v3 := 000 00100 v4 := 010 00010 v5 := 110 00001 v1' := 010 10000
v2' := 002 01000 v3' := 100 00100 v4' := 000 00010 v5' := 001 00001 b := 444 11111 c1:= 100 00000 d1:= 200 00000 c2:= 010 00000 d2:= 020 00000 c3:= 001 00000 A clauses NP-complete, BNPand A B values B also NP-complete. m in n var.s 2n+2m+1 n+m dec.digits