算法设计与分析算法设计与分析 (1).pdf

1Chapter 8NP and ComputationalIntractabilitySlides by Kevin Wayne.Copyright 2005 Pearson-Addison Wesley.All rights reserved.8.3 Definition of NP3Decision ProblemsDecision problem.X is a set of strings.Instance:string s.Algorithm A solves problem X:A(s)=yesiff s X.Polynomial 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.PRIMES:X=2,3,5,7,11,13,17,23,29,31,37,.Algorithm.Agrawal-Kayal-Saxena,2002 p(|s|)=|s|8.4Definition of PP.Decision problems for which there is a poly-time algorithm.ProblemDescriptionAlgorithmYesNoMULTIPLEIs x a multiple of y?Grade school division51,1751,16RELPRIMEAre x and y relatively prime?Euclid(300 BCE)34,3934,51PRIMESIs x prime?AKS(2002)5351EDIT-DISTANCEIs the edit distance between x and y less than 5?Dynamic programmingniether neitheracgggt tttttaLSOLVEIs there a vector x that satisfies Ax=b?Gauss-Edmonds elimination0112420315,4236100111011,1115NPCertification algorithm intuition.Certifier doesnt determine whether s X on its own;rather,it checks a proposed proof t that s X.Def.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 problems for which there exists a poly-time certifier.Remark.NP stands for nondeterministic polynomial-time.C(s,t)is a poly-time algorithm and|t|p(|s|)for some polynomial p().6Certifiers and Certificates:CompositeCOMPOSITES.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|.Certifier.Instance.s=437,669.Certificate.t=541 or 809.Conclusion.COMPOSITESis in NP.437,669=541 809boolean C(s,t)if(t 1 or t s)return falseelse if(s is a multiple of t)return trueelse return false7Certifiers and Certificates:3-SatisfiabilitySAT.Given a CNF formula,is there a satisfying assignment?Certificate.An assignment of truth values to the n boolean variables.Certifier.Check that each clause in has at least one true literal.Ex.Conclusion.SATis in NP.x1 x2 x3x1 x2 x3x1 x2 x4 x1 x3 x4x11,x21,x3 0,x41instance scertificate t8Certifiers and Certificates:Hamiltonian CycleHAM-CYCLE.Given an undirected graph G=(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-CYCLEis in NP.instance scertificate t9P,NP,EXPP.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.Claim.P NP.Pf.Consider any problem X in P.By definition,there exists a poly-time algorithm A(s)that solves X.Certificate:t=,certifier C(s,t)=A(s).Claim.NP EXP.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 yesfor any of these.10The Main Question:P Versus NPDoes P=NP?Cook 1971,Edmonds,Levin,Yablonski,GdelIs the decision problem as easy as the certification problem?Clay$1 million prize.If yes:Efficient algorithms for 3-COLOR,TSP,FACTOR,SAT,If no:No efficient algorithms possible for 3-COLOR,TSP,SAT,Consensus opinion on P=NP?Probably no.EXPNPPIf P NPIf P=NPEXPP=NPwould break RSA cryptography(and potentially collapse economy)8.4 NP-Completeness12Polynomial TransformationDef.Problem X polynomial reduces(Cook)to problem 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 any input x to X,we can construct an input y such that x is a yesinstance of X iff y is a yesinstance of Y.Note.Polynomial transformation is polynomial reduction with just one call to oracle for Y,exactly at the end of the algorithm for X.Almost all previous reductions were of this form.Open question.Are these two concepts the same?we require|y|to be of size polynomial in|x|13NP-CompleteNP-complete.A problem Y in NP with the property that for every problem X in NP,X pY.Theorem.Suppose Y is an NP-complete problem.Then Y is solvable in poly-time iff P=NP.Pf.If P=NP then Y can be solved in poly-time since Y is in NP.Pf.Suppose Y can be solved in poly-time.Let X be any problem in NP.Since X pY,we can solve X inpoly-time.This implies NP P.We already know P NP.Thus P=NP.Fundamental question.Do there exist natural NP-complete problems?14The First NP-Complete ProblemTheorem.SAT(3-SAT)is NP-complete.Cook 1971,Levin 197315Establishing NP-CompletenessRecipe to establish NP-completeness of problem Y.Step 1.Show that Y is in NP.Step 2.Choose an NP-complete problem X.Step 3.Prove that X pY.Justification.If X is an NP-complete problem,and Y is a problem in NP with the property that X PY then Y is NP-complete.Pf.Let W be any problem in NP.Then W P X P Y.By transitivity,W P Y.Hence Y is NP-complete.16Some NP-Complete ProblemsSix basic genres of NP-complete problems and paradigmatic examples.Packing problems:INDEPENDENT SET.Covering problems:SET-COVER,VERTEX-COVER.Constraint satisfaction problems:SAT,3-SAT.Sequencing problems:HAMILTONIAN-CYCLE,TSP.Numerical problems:SUBSET-SUM,PARTITION.Practice.Most NP problems are either known to be in P or NP-complete.Notable exceptions.Factoring,graph isomorphism,Nash equilibrium.Basic genres.Packing problems:INDEPENDENT SET.Covering problems:SET-COVER,VERTEX-COVER.Constraint satisfaction problems:SAT,3-SAT.Sequencing problems:HAMILTONIAN-CYCLE,TSP.Numerical problems:SUBSET-SUM,PARTITION.8.5 Sequencing Problems18Hamiltonian CycleHAM-CYCLE:given an undirected graph G=(V,E),does there exist a simple cycle that contains every node in V.135132424NO:bipartite graph with odd number of nodes.19Directed 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 PHAM-CYCLE.Pf.Given a directed graph G=(V,E),construct an undirected graph G with 3n nodes.vabcdevinaoutboutcoutdineinGGvvout20Directed Hamiltonian CycleClaim.G has a Hamiltonian cycle iff G does.Pf.Suppose G has a directed Hamiltonian cycle.Then G has an undirected Hamiltonian cycle(same order).Pf.Suppose G has an undirected Hamiltonian cycle.must visit nodes in G using one of following two orders:,B,G,R,B,G,R,B,G,R,B,B,R,G,B,R,G,B,R,G,B,Blue nodes in make up directed Hamiltonian cycle in G,or reverse of one.213-SAT Reduces to Directed Hamiltonian CycleClaim.3-SATPDIR-HAM-CYCLE.Pf.Given an instance of 3-SAT,we construct an instance of DIR-HAM-CYCLEthat has a Hamiltonian cycle iff is satisfiable.Construction.First,create graph that has 2nHamiltonian cycles which correspond in a natural way to 2npossible truth assignments.223-SAT Reduces to Directed Hamiltonian CycleConstruction.Given 3-SATinstance with n variables xiand k clauses.Construct G to have 2nHamiltonian cycles.Intuition:traverse path i from left to right set variable xi=1.st3k+3x1x2x3233-SAT Reduces to Directed Hamiltonian CycleConstruction.Given 3-SATinstance with n variables xiand k clauses.For each clause:add a node and 6 edges.stclause nodeclause node3211VVxxxC3212VVxxxCx1x2x3243-SAT Reduces to Directed Hamiltonian CycleClaim.is satisfiable iff G has a Hamiltonian cycle.Pf.Suppose 3-SATinstance has satisfying assignment x*.Then,define Hamiltonian cycle in G as follows:if x*i=1,traverse row i from left to rightif x*i=0,traverse row i from right to leftfor each clause Cj,there will be at least one row i in which we are going in correct direction to splice node Cj into tour253-SAT Reduces to Directed Hamiltonian CycleClaim.is satisfiable iff G has a Hamiltonian cycle.Pf.Suppose G has a Hamiltonian cycle.If enters clause node Cj,it must depart on mate edge.thus,nodes immediately before and after Cj are connected by an edge e in Gremoving Cj from cycle,and replacing it with edge e yields Hamiltonian cycle on G-Cj Continuing in this way,we are left with Hamiltonian cycle inG-C1,C2,.,Ck.Set x*i=1 iff traverses row i left to right.Since visits each clause node Cj,at least one of the paths is traversed in correct direction,and each clause is satisfied.26Traveling Salesperson ProblemTSP.Given a set of n cities and a pairwise distance function d(u,v),is there a tour of length D?HAM-CYCLE:given a graph G=(V,E),does there exists a simple cycle that contains every node in V?Claim.HAM-CYCLEPTSP.Pf.Given instance G=(V,E)of HAM-CYCLE,create n cities with distance functionTSP instance has tour of length n iff G is Hamiltonian.Remark.TSP instance in reduction satisfies-inequality.d(u,v)1if(u,v)E 2if(u,v)EBasic genres.Packing problems:INDEPENDENT SET.Covering problems:SET-COVER,VERTEX-COVER.Constraint satisfaction problems:SAT,3-SAT.Sequencing problems:HAMILTONIAN-CYCLE,TSP.Numerical problems:SUBSET-SUM,PARTITION.8.8 Numerical Problems28Subset SumSUBSET-SUM.Given natural numbers w1,wnand an integer W,is there a subset that adds up to exactly W?Ex:1,4,16,64,256,1040,1041,1093,1284,1344,W=3754.Yes.1+16+64+256+1040+1093+1284=3754.Remark.With arithmetic problems,input integers are encoded in binary.Polynomial reduction must be polynomial in binary encoding.Claim.3-SAT PSUBSET-SUM.Pf.Given an instance of 3-SAT,we construct an instance of SUBSET-SUMthat has solution iff is satisfiable.29Subset SumConstruction.Given 3-SAT instance with n variables and k clauses,form 2n+2k decimal integers,each of n+k digits,as illustrated below.Claim.is satisfiable iff there exists a subset that sums to W.Pf.No carries possible.C1 x y zC2 x y zC3 x y zdummies to getclause columnsto sum to 4yxz000010000200000100001001010011010100100101100010001110 xyzC1C2C3000002000001000020111444 x y zW102001001,00110,01110,100100,101100,0101,1102120111,44430PartitionSUBSET-SUM.Given natural numbers w1,wnand an integer W,is there a subset that adds up to exactly W?PARTITION.Given natural numbers v1,vm,can they be partitioned into two subsets that add up to the same value?Claim.SUBSET-SUMPPARTITION.Pf.Let W,w1,wnbe an instance of SUBSET-SUM.Create instance of PARTITIONwith m=n+2 elements.v1=w1,v2=w2,vn=wn,vn+1=2 iwi-W,vn+2=iwi+WThere exists a subset that sums to W iff there exists a partition since two new elements cannot be in the same partition.vn+2=iwi+Wvn+1=2 iwi-W iwi-WWsubset Asubset Bivi31Polynomial-Time Reductions3-SATDIR-HAM-CYCLEINDEPENDENT SETVERTEX COVERDick Karp(1972)1985 Turing AwardHAM-CYCLETSPSUBSET-SUMSCHEDULINGSET COVERpacking and coveringsequencingnumericalconstraint satisfaction8.9 co-NP and the Asymmetry of NP33Asymmetry of NPAsymmetry of NP.We only need to have short proofs of yesinstances.Ex 1.SAT vs.TAUTOLOGY.Can prove a CNF formula is satisfiable by giving such an assignment.How could we prove that a formula is not satisfiable?Ex 2.HAM-CYCLEvs.NO-HAM-CYCLE.Can prove a graph is Hamiltonian by giving such a Hamiltonian cycle.How could we prove that a graph is not Hamiltonian?Remark.SATis NP-complete,but how do we classify TAUTOLOGY?34NP and co-NPNP.Decision problems for which there is a poly-time certifier.Ex.SAT,HAM-CYCLE,COMPOSITES.Def.Given a decision problem X,its complement X is the same problem with the yesand noanswers reverse.Ex.X=0,1,4,6,8,9,10,12,14,15,Ex.X=2,3,5,7,11,13,17,23,29,co-NP.Complements of decision problems in NP.Ex.TAUTOLOGY,NO-HAM-CYCLE,PRIMES.35Fundamental question.Does NP=co-NP?Do yesinstances have succinct certificates iff noinstances do?Consensus opinion:no.Theorem.If NP co-NP,then P NP.Pf idea.P is closed under complementation.If P=NP,then NP is closed under complementation.In other words,NP=co-NP.This is the contrapositive of the theorem.NP=co-NP?