-算法和程序设计-NP问题-精选.ppt

1、1NP and ComputationalIntractability叶德仕yedeshigmail2 Decision ProblemsDecision problem.(the answer is simply yes or no)X is a set of strings.Instance:string s.Algorithm A solves problem X:A(s)=yes iff s X.Optimization problems.in which each feasible(i.e.,legal)solution has an associated value,and we

2、wish to find the feasible solution with the best value.3Polynomial time.Algorithm A runs in poly-time if for every string s,A(s)terminates in at most p(|s|)steps,where p(.)is some polynomial.Certification algorithm intuition.Certifier views things from managerial viewpoint.Certifier doesnt determine

3、 whether s X on its own;rather,it checks a proposed certificate t that s X.i.e.,certifier verify the proposed solution t and the instance s whether C(s,t)is yes.4Def.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.NP.Decision pr

4、oblems for which there exists a poly-time certifier.Remark.NP stands for nondeterministic poly-time.5 Certifiers and Certificates:Composite(合数)COMPOSITES.Given an integer s,is s composite?Certificate.A nontrivial factor t of s.Note that such a certificate exists iff s is composite.Moreover|t|s|.Cert

5、ifier.boolean C(s,t)if(t 1 or t s)return falseelse if(s is a multiple of t)return trueelse return false6ExampleInstance.s=437,669.Certificate.t=541 or 809.Conclusion.COMPOSITES is in NP.7 Certifiers and Certificates:3-SatisfiabilitySAT.Given a CNF formula,is there a satisfying assignment?Certificate

6、.An assignment of truth values to the n boolean variables.Certifier.Check that each clause in has at least one true literal.123123124134()()()()xxxxxxxxxxxx12341,1,0,1xxxxInstance:Certificate:Conclusion.SAT is in NP.8 Certifiers and Certificates:Hamiltonian CycleHAM-CYCLE.Given an undirected graph G

7、=(V,E),does there exist a simple cycle C that visits every node?Certificate.A permutation of the n nodes.Certifier.Check that the permutation contains each node in V exactly once,and that there is an edge between each pair of adjacent nodes in the permutation.Conclusion.HAM-CYCLE is in NP.9P,NP,EXPP

8、.Decision problems for which there is a poly-time algorithm.EXP.Decision problems for which there is an exponential-time algorithm.NP.Decision problems for which there is a poly-time certifier.10Claim.Pf.Consider any problem X in P.By definition,there exists a poly-time algorithm A(s)that solves X.C

9、ertificate:certifier C(s,t)=A(s).Claim.Pf.Consider any problem X in NP.By definition,there exists a poly-time certifier C(s,t)for X.To solve input s,run C(s,t)on all strings t with|t|p(|s|).Return yes,if C(s,t)returns yes for any of these.!PNPNPEXP11The Main Question:P Versus NPDoes P=NP?Cook 1971,E

10、dmonds,Levin,Yablonski,GdelIs the decision problem as easy as the certification problem?Clay$1 million prize.EXP NPPEXP P=NPIf P=NPIf P NP12A formual-language FrameworkAn alphabet is a finite set of symbols.A language L over is any set of strings made up of symbols from.For example,=0,1,L=10,11,101,

11、111,1011,1101,10001,.L is the language of binary representations of prime numbers Denote empty string by Denote empty language by 13The language of all strings over is denoted*.For example =0,1,then*=,0,1,00,01,10,11,000,.is the set of all binary strings.Every language L over is a subset of*.14Set-t

12、heoretic operations complement of L by*-L.The concatenation of two languages L1 and L2 is the language L=x1x2:x1 L1 and x2 L2.The closure or Kleene star of a language L is the language L*=L L2 L3 ,where Lk is the language obtained by concatenating L to itself k times.15Decision problem and languaget

13、he set of instances for any decision problem Q is simply the set*,where =0,1.Since Q is entirely characterized by those problem instances that produce a 1(yes)answer,we can view Q as a language L over =0,1,where L=x *:Q(x)=1.Example:PATH=G,u,v,k:G=(V,E)is an undirected graph,u,v V,k 0 is an integer,

14、and there exists a path from u to v in G consisting of at most k edges.16We say that an algorithm A accepts a string x 0,1*if,given input x,the algorithms output A(x)is 1.The language accepted by an algorithm A is the set of strings L=x 0,1*:A(x)=1 An algorithm A rejects a string x if A(x)=0.A langu

15、age L is decided by an algorithm A if every binary string in L is accepted by A and every binary string not in L is rejected by A.17A language L is accepted in polynomial time by an algorithm A if it is accepted by A and if in addition there is a constant k such that for any length-n string x L,algo

16、rithm A accepts x in time O(nk).A language L is decided in polynomial time by an algorithm A if there is a constant k such that for any length-n string x 0,1*,the algorithm correctly decides whether x L in time O(nk).To accept a language,an algorithm need only worry about strings in L,but to decide

17、a language,it must correctly accept or reject every string in 0,1*.18Class PP=L 0,1*:there exists an algorithm A that decides L in polynomial time 19Polynomial-time verification For example,suppose that for a given instance G,u,v,k of the decision problem PATH,We are also given a path p from u to v.

18、We can easily check whether the length of p is at most k.So,we can view p as a certificate that the instance indeed belongs to PATH.20 Verification algorithms define a verification algorithm as being a two-argument algorithm A,where one argument is an ordinary input string x and the other is a binar

19、y string y called a certificate.A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x,y)=1.The language verified by a verification algorithm A is L=x 0,1*:there exists y 0,1*such that A(x,y)=1.21Class NPThe complexity class NP is the class of languages t

20、hat can be verified by a polynomial-time algorithm More precisely,a language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and constant c such that L=x 0,1*:there exists a certificate y with|y|=O(|x|c)such that A(x,y)=1.We say that algorithm A verifies language L

21、 in polynomial time.22class co-NP That is,does L NP imply We can define the complexity class co-NP as the set of languages L such that?LNPLNPP=NP=co-NPNP=co-NPPco-NPP=NP co-NPNPco-NPNP co-NPNPP23NP-completeness and reducibility Polynomial TransformationDef.Problem X polynomial reduces(Cook)to proble

22、m Y if arbitrary instances of problem X can be solved using:Polynomial number of standard computational steps,plusPolynomial number of calls to oracle that solves problem Y.Def.Problem X polynomial transforms(Karp)to problem Y if given anyinput x to X,we can construct an input y in polynomial time s

23、uch that x is a yes instance of X iff y is a yes instance of Y.24we say that a language L1 is polynomial-time reducible to a language L2 written L1 P L2,if there exists a polynomial-time computable function f:0,1*0,1*such that for all x 0,1*,We call the function f the reduction function,and a polyno

24、mial-time algorithm F that computes f is called a reduction algorithm.12if and only if()xLf xL25NP-CompleteNP-complete.A problem Y in NP with the property that for every problem X in NP,X P Y.A language L 0,1*is NP-complete ifL NP,andL P L for every L NP.26Lemma.If L1,L2 0,1*are languages such that

25、L1 P L2,then L2 P implies L1 P.FA2xf(x)2,()yes f xL1,yes xL2,()no f xL2,no xLA127Theorem.If any NP-complete problem is polynomial-time solvable,then P=NP.Pf.Suppose that L P and also that L NPC.For any L NP,we have L P L by property 2 of the definition of NP-completeness.Thus,by above Lemma,we also

26、have that L P,which proves the theorem.NPPNPCIf P NP28 Circuit SatisfiabilityCIRCUIT-SAT.Given a combinational circuit built out of AND,OR,and NOT gates,is there a way to set the circuit inputs so that the output is 1?10?Yes:101Output29The First NP-Complete ProblemTheorem.CIRCUIT-SAT is NP-complete.

27、Cook 1971,Levin 1973Pf.The circuit-satisfiability problem belongs to the class NP.show that every language in NP is polynomial-time reducible to CIRCUIT-SAT.30 Establishing NP-CompletenessMethod for showing that a problem Y is NP-complete Show that Y is in NP.Choose an NP-complete problem X.X P Y Ju

28、stification.If X is a problem such that Y P X for some Y NPC,then X is NP-hard.Moreover,if X NP,then L NPC.31 3-SAT is NP-CompleteTheorem.3-SAT is NP-complete.Pf.Suffices to show that CIRCUIT-SAT P 3-SAT since 3-SAT is in NP.Let K be any circuitCreate a 3-SAT variable xi for each circuit element i.x

29、5x4x3x1x2x02323232,xxaddclausesxxxx 32Proof.Con.14514151453,xxxaddclausesxxxxxxx01201020123,xxxaddclausesxx xxxxx550001xxxx 33Proof.Con.Final step:turn clauses of length 3 into clauses of length exactly 3!If C has 3 distinct literals,done.If C has 2 distinct literals if C=(L1 L2),then include(L1 L2

30、p)(L1 L2 p)If C has just 1 distinct literal l(l p q)(l p q)(l p q)(l p q)34 3-CNF satisfiability A boolean formula is in conjunctive normal form,or CNF,if it is expressed as an AND of clauses,each of which is the OR of one or more literals.3-CNF,if each clause has exactly three distinct literals.Exa

31、mple:(x1 x1 x2)(x3 x2 x4)(x1 x3 x4)35Theorem.Satisfiability of boolean formulas in 3-conjunctive normal form is NP-complete.36 The clique problem A clique in an undirected graph G=(V,E)is a subset V V of vertices,each pair of which is connected by an edge in E.In other words,a clique is a complete s

32、ubgraph of G.The size of a clique is the number of vertices it contains.The clique problem is the optimization problem of finding a clique of maximum size in a graph.As a decision problem,we ask simply whether a clique of a given size k exists in the graph.The formal definition is CLIQUE=G,k:G is a

33、graph with a clique of size k.37Clique problemTheorem.The clique problem is NP-complete.Pf.CLIQUE is in NP,for a given graph G=(V,E),we use the set V V of vertices in the clique as a certificate for G.Checking whether V is a clique can be accomplished in polynomial time by checking whether,for each

34、pair u,v V,the edge(u,v)belongs to E.next prove that 3-CNF-SAT P CLIQUE reduction algorithm:Let =C1 C2 Ck be a boolean formula in 3-CNF with k clauses.We shall construct a graph G such that is satisfiable if and only if G has a clique of size k.38 Construct of graph GThe graph G=(V,E)is constructed

35、as follows.For each clause Cr=(r1,r2,r3),we place a triple of vertices vr1,vr2,vr3 in V.We put an edge between two vertices vri,vsj if both of the following hold:vri and vsj are in different triples,that is,r s,their corresponding literals are consistent,that is ri is not the negation of sj.This gra

36、ph can easily be computed from in polynomial time 39Example=(x1 x2 x3)(x1 x2 x3)(x1 x2 x3),40Proof.Con.We must show that this transformation of into G is a reduction First,suppose that has a satisfying assignment.Then each clause Cr contains at least one literal rj that is assigned 1.and each such l

37、iteral corresponds to a vertex vrj.Picking one such true literal from each clause yields a set V of k vertices.We claim that V is a clique.For any two vertices vri,vsj where r s,both corresponding literals ri rand sj are mapped to 1 by the given satisfying assignment,and thus the literals cannot be

38、complements.41Proof.Con.Conversely,suppose that G has a clique V of size k.No edges in G connect vertices in the same triple,and so V contains exactly one vertex per triple.We can assign 1 to each literal ri such that vrj V,then assigning 1 to both a literal and its complement can not happen,since G

39、 contains no edges between inconsistent literals.Each clause is satisfied,and so is satisfiedAny variables that do not correspond to a vertex in the clique may be set arbitrarily 42 The vertex-cover problem A vertex cover of an undirected graph G=(V,E)is a subset V V such that if(u,v)E,then u V or v

40、 V(or both).A vertex cover for G is a set of vertices that covers all the edges in E.As a decision problem,we defineVERTEX-COVER=G,k:graph G has a vertex cover of size k.43 Vertex-cover is NPCTheorem.The vertex-cover problem is NP-complete.We first show that VERTEX-COVER NP.Given a graph G=(V,E)and

41、an integer k.Certificate is the vertex cover V V itself.The verification algorithm affirms that|V|=k,and then it checks,for each edge(u,v)E,that u V or v V.This verification can be performed straightforwardly in polynomial time.44The vertex-cover problem is NP-hard by showing that CLIQUE P VERTEX-CO

42、VER This reduction is based on the notion of the complement of a graph.Given an undirected graph G=(V,E),we define the complement of G,the graph containing exactly those edges that are not in G.45Example:complement of G46Vertex-coverThe reduction algorithm takes as input an instance G,k of the cliqu

43、e problem.It computes the complement ,which is easily done in polynomial time.The output of the reduction algorithm is the instance of the vertex-cover problem.The graph G has a clique of size k if and only if the graph has a vertex cover of size|V|-k.,|G VkGG47Vertex-coverSuppose that G has a cliqu

44、e V V with|V|=k.We claim that V-V is a vertex cover in .Let(u,v)be any edge in.Then,(u,v)E,which implies that at least one of u or v does not belong to V,since every pair of vertices in V is connected by an edge of E.Equivalently,at least one of u or v is in V-V,which means that edge(u,v)is covered

45、by V-V.Hence,the set V-V,which has size|V|-k,forms a vertex cover for GG48Vertex-cover con.Conversely,suppose that has a vertex cover V V,where|V|=|V|-k.Then,for all u,v V,if(u,v),then u V or v V or both.For all u,v V,if u V and v V,then(u,v)E.In other word,V-V is a clique,and it has size|V|-|V|=k.G

46、49Hamiltonian CycleHAM-CYCLE:given an undirected graph G=(V,E),does there exist a simple cycle that contains every node in V.YES:vertices and faces of a dodecahedron.50Hamiltonian CycleHAM-CYCLE:given an undirected graph G=(V,E),does there exist a simple cycle that contains every node in V.NO:bipart

47、ite graph with odd number of nodes.51Directed Hamiltonian CycleDIR-HAM-CYCLE:given a digraph G=(V,E),does there exists a simple directed cycle that contains every node in V?Claim.DIR-HAM-CYCLE P HAM-CYCLE.VVinVoutV523-SAT Reduces to Directed Hamiltonian CycleClaim.3-SAT P DIR-HAM-CYCLE533-SAT Reduce

48、s to Directed Hamiltonian CycleClaim.3-SAT P DIR-HAM-CYCLEPf.Given an instance of 3-SAT,we construct an instance of DIRHAM-CYCLE that has a Hamiltonian cycle iff is satisfiable.Construction.First,create graph that has 2n Hamiltonian cycles which correspond in a natural way to 2n possible truth assig

49、nments.Intuition:traverse path i from left to right iff set variable xi=1.54Hamiltonian PathHAM-CYCLE p HAM-PATH:55Longest PathSHORTEST-PATH.Given a digraph G=(V,E),does there exists a simple path of length at most k edges?LONGEST-PATH.Given a digraph G=(V,E),does there exists a simple path of lengt

50、h at least k edges?56Longest PathClaim.HAM-CYCLE p Longest-PathLet G=(V,E)be an instance of HAM-CYCLE.If the longest-simple-cycle in G is of length|V|,then every vertex was visited and thus there is a Hamiltonian cycle in G.Reduction:Compute the longest-simple-cycle in G.If the length of this cycle=