# CS422 Theory of Computation

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

## Recently Viewed Presentations

• Structural Mechanics 4Shear Force, Bending Moment and Deflection of Beams. 20 kN. 2.00m. 3.00m. R. A. R. B
• Copy of Powerpoint and Excel Models are available at: Enrollment Projections and the Budget Process: A Technique for Smart Planning SCUP-39 Annual Conference Toronto, Canada July 20, 2004 Summary of Presentation Enrollment Projection Methods UD Enrollment Model Brief Demo of...
• Welfare Transition Program. Work Registration Process. Welcome to the Department of Economic Opportunity's Training on The Welfare Transition Program's Work Registration process.
• Comparator units were chosen for each UTM department (ie: Rotman for Management; Astronomy, Chemistry, Geology & Physics for CPS) Only primary Council programs were included in the analysis (SSHRC Standard, NSERC Discovery & CIHR Operating) to create a reasonably equitable...
• Working with WHO, Red Cross/Red Crescent, Ministries of Health in E/S Africa. Ministers are using for early warning systems. ... It is demand-driven, created at the request of the El Salvadoran Government and still in high demand; the El Salvador...
• NUCLEUS is preparing for mitosis. Good bye to the nucleolus and nuclear envelope. Hello condensed chromosomes ! September 15, 2011 View photos of NUCLEUS Send the NUCLEUS a message Poke message NUCLEUS is preparing for mitosis. Good bye to the...
• SCCOOS Web Site Real-time Oil Spill Response Scenario Scenario There was an oil spill near Rancho Palos Verdes at 33.7201 N, 118.3458 W today. Use the wave conditions web page, meteorological conditions web page, surface current mapping web page, and...
• Poetry Terms Alliteration: The repetition of sounds in a group of words as in "Peter Piper Picked a Peck of Pickled Peppers." Allusion: A reference to a person, place, or thing--often literary, mythological, or historical.