信息论基础与编码 (1).pdf

《信息论基础与编码 (1).pdf》由会员分享，可在线阅读，更多相关《信息论基础与编码 (1).pdf（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Lecture 11:Computational Complexity TheoryBasic definitions:problem size,basic operations,big O notationP and NP classesExamples:Maximum Clique Integer Linear Programming Satisfiability problem,Travelling Salesman ProblemPolynomial reductionsNP-complete problems,Cooks Theorem1DefinitionsProblem size

2、s:Graph:G=(V,E);size=|V|+|E|Sorting:a1,a2,.,an;size:n,orPilog|ai|,orn maxlog|ai|Basic operations:Graph search:examine the adjacent nodes Sorting:comparison,swapping positions of two entries Matrix problems:arithmetic operations,+,2Complexity TheoryComplexity of an algorithmtotal number of basic oper

3、ations to solve a problem of a given size Sorting:O(n2)(Bubble sort)O(nlog n)(Heap sort)Breath-first search:O(|E|)+O(|V|)Depth-first search:O(|E|+|V|)Big“O”notations:asymptotic,inexact,convenientPolynomial time algorithms:complexity is polynomial in sizeMatrix multiplication:Ann,BnnBasic operations:

4、+,Direct method:O(n3)Strassen:O(n2.67)3NP-Complete ProblemsSo far our main objective has been to design efficient algorithmSuccesses:convexity,LP,SOCP,SDP,interior point methods in the continuous optimizationdomain shortest path,bipartite matching,non-bipartite matching in the discrete optimizationd

5、omain sorting,max-flow,minimum weight spanning treeFailures:Integer LP,non-convex QP,TSP,satisfiability problem,etcno efficient algorithms are knownNP-completeness problems as hard as any reasonable problemse.g.TSP:haunted two-three generations of brilliant mathematicians4NP-Complete ProblemsNP-Comp

6、lete problems has the following interesting properties:No NP-Complete problem can be solved by any known polynomial algorithm(persistsdespite efforts by many brilliant researchers)If there is a polynomial algorithm for any NP-Complete problem,then there arepolynomial time algorithms for all NPC prob

7、lemsPractical significance of the notion NPC lies in the wide spread belief that NPC problemsare inherently intractableImplications:once a problem is shown to be NPC,we generally are ready accept lessambitious goals:(polynomial time)heuristics or approximation algorithms5Formulating Optimization Pro

8、blemsAn optimization problem consists of a set of instancesS:set of instances Each instance inStakes the form(F,C),withF:feasible solution set,C:costfunction s.t.C:F 7RF,Care usually given by two algorithmsaF,aCaF:given a potential solutionfand parameter setS,aFwill determine iff FaC:computes costC(

9、f),for any givenfand a set of parametersQ6Some ExamplesExample 1:An instance of Travelling Salesman Problem(TSP)withncities has aparameter setSbeing the integern;its parameterQis the distance matrixdijnn.aF:given an objectfand integern,determine whetherfis a tour ofncities(i.e.,a cyclic permutation

10、of1,2,.,n)aC:givendijnn,computeC(f)by summing all entries ofdijnnthatcorrespond to distances traversed by the tour7Some ExamplesExample 2:Maximum CliqueGiven a graphG=(V,E),find the largest subsetC Vs.t.all distinctu,v C,(u,v)E.The parameter setSis the graphG=(V,E);Qempty.aF:check if a subsetC Vis a

11、 cliqueaC:counts the no.of vertices inC.Example 3:Integer linear programming:minimizecTxsubject toAx=b,x 0,x:integeraF:has as parameterA,baC:has as parametercNote that in all 3 examplesaF,aCare polynomial-time algorithms.8Combinatorial Optimization ProblemsA combinatorial optimization problem has th

12、ree versions.Optimization version:Given representation ofS,Qfor the algorithmaFaC,find the optimal feasiblesolution.Evaluation version:GivenS,Q,find the cost of the optimal solutionRecognition version:Given an instance ofS,Q,and an integerL,is there a feasiblesolutionf F,s.t.c(f)L9Comments on Three

13、VersionsIfaCis polynomial-time,then evaluation version is easier to solve then the optimizationversion.Recognition version requires only YES or NO answer.Recognition version is not much harder than the evaluation version,since we only needto compareC(f)toL.Thus,Optimization versionEvaluation version

14、Recognition version.LetTo(n),Te(n)andTr(n)denote the complexity of solving optimization,evaluation and recognition version respectively.Using binary search inL,wecan haveTe(n)=log C(f)Tr(n)IfC(f)has polynomial size,then polynomial bound onTr(n)implies polynomialbound onTe(n).10Dynamic ProgrammingOpt

15、imization version can be solved by an algorithm for Evaluation version via DynamicProgrammingSuppose we have cliquesize procedure which,givenG,will evaluate the maximum cliqueinG.Procedure maxclique(G):ifGhas number nodes then returnelsebeginletvbe a node s.t.cliquesize(G(v)=cliquesize(G),whereG(v)i

16、s the subgraph ofGconsisting ofvand all its adjacentnodes;returnv maxclique(G(v)v);end11Commentsmaxclique is a recursive procedure;uses cliquesize(G)as an oraclemaxclique first finds a nodevofGthat certainly participates in a maximum cliqueWe do this by checking the cliquesize is not reduced if we o

17、mit all vertices nonadjacenttov;this meansvis a vertex of some maximum clique.If clique-size procedure has running timeC(n)=the complexity of maxcliqueT(n)can be derived as follows:T(0)=O(1),T(n)(n+1)C(n)+T(n 1)+O(n)This impliesT(n)=On2 C(n)12Polynomial TimeIf cliquesize operates in polynomial time,

18、thenT(n)is also polynomial time=all three versions can be solved efficiently if any one of them can be solvedefficientlySimilar techniques apply to TSPThus,in our study of computational complexity,we can restrict our attention toRecognition version of optimization problems:Satisfiability problem(SAT

19、):is a Boolean formula satisfiable?Hamiltonian circuit:Given a graphG,is there a circuit inGthat visits all nodesexactly once?13Polynomial Time ClassP:class of recognition problems that can be solved by a polynomial time algorithm;defined in terms of any mathematical formalism for algorithm,such as

20、Turing machine.It turns out“polynomial-time”is extremely stable with respect to the variation in thedetails of computational methods14Examples in PGraph connectedness:Given a graphG,isGconnected?Path in a digraph:Given a digraphD=(V,A),and two subsetsS,T V,isthere a path from a vertex ofSto a vertex

21、 ofTinD?maximum matching:Given a graphGand an integerk,is there a matching inGwithkor more edges?minimum weight spanning tree:Given a connected graphG=(V,E),a costfunctionddefined onE,and an integerL,is there a spanning tree ofGwith costLor less?15NP ClassNP(Nondeterministic Polynomial-time):a riche

22、r class than P(seemingly at least)Dont require every instance to be answered in polynomial time by some algorithms Simply require that,ifxis a yes instance,there exists a concise certificate(polynomial size)forx,which can be checked in polynomial time.Example:Maximum CliqueGivenG=(V,E),an integerk,i

23、s there a clique of sizek?It is not known if clique is in P.Obvious way to solve this problem would be to examine all|V|ksubsets ofV,with cordinalityk.But this is exponential in size,therefore in time as well.16NPNonetheless,Maximum Clique is in NP.To see this,given a yes instance:G=(V,E)and integer

24、k,s.t.Gdoes contain a clique ofksize,a concise certificate is a list ofknodes which is efficiently checkable for validity.TSP:Given an integern,a distance matrixdijnn,an integerL,find whetheracyclic permutation(certificate)such thatPni=1di,(i)L.TSP is in NP:Given a yes instancex=(n,dij,L)of TSP,we c

25、an easily check ifa toursatisfiesPni=1di,(i)Lin polynomial time.Satisfiability(SAT):Given a set of clausesc1,c2,cm,involving Boolean variablesx1,xn,checkif therea truth assignment tox1,xn,such thatc1,cmare all satisfied.SAT problem is in NP:Given a yes instance of the SAT problem,a certificate-check

26、ingalgorithm simply makes sure all clauses are legitimate involving variablesx1,xnand all clauses come out true under a truth assignment(certificate).17Polynomial ReductionImportant:to show a problem is in NP,no need to show how a certificatec(x)isgenerated fromx.One simply shows the existence of on

27、e suchc(x).PNP:Suppose there is a polynomial time algorithmaAfor problemA.Given a yes instancexofA,aAwill operate onxfor a polynomial number of stepsand answer yes,then the record of this operation ofaAonxis a valid certificatec(x).One only has to check all steps performed byaAonxare valid execution

28、s ofaA.Polynomial reduction:LetA1,A2be two recognition problems(yes-no problems)“A1reduces in polynomialtime toA2”iffa polynomial time algorithma1forA1that uses as a subroutine atunit cost a(hypothetical)algorithma2forA2,we calla1a polynomial time reductionofA1toA2.18Polynomial ReductionProposition:

29、IfA1polynomially reduces toA2,and therea polynomial time algorithmforA2,then therea polynomial algorithm forA1.Proof:LetPi(n)be the complexity of algorithmai.Thenp(n)=P1(n)P2(P1(n),where we noteP1(n)is the maximum number of calls,and is also the max input size toa2.A special polynomial reduction:We

30、say a recognition problemA1polynomially transforms to another recognitionproblemA2,if given any inputxforA1,we can construct within polynomial time(in|x|)such thatxis yes forA1iffy is yes forA2.Polynomial-time transformation is just a polynomial reduction with one call of thesubroutine forA2,exactly

31、 at the end of the algorithm forA1.19NP and NPCA recognition problemA NP is called NP-complete if all other problems in NPpolynomially transform toA.Thus,a problemAis NPC,then any polynomial algorithm forAimplies polynomial-time algorithms for all problems in NP(including the hard problems like SAT,

32、TSP,Clique,ILP,etc).Cooks theorem:SAT is NPC(uses details of Turing machine model).NPCPNPP v.s.NP20Some Other NP-complete Problems3-SAT:SATc1,cm,with eachciinvolving at most 3 literals.1.Ifcihas three literals,do nothing.2.Ifcihas more than three literals,sayci=(1+2+k),k 3,wereplacecibyk 2clauses(1+

33、2+x1)(x1+3+x2)(x2+4+x3)(xk3+k1+k),wherex1,xk3are new variables.3.It is not hard to see that these new clauses are satisfiable if and only ifciis.21Vertex Cover is NP-CompleteVertex Cover:Given graphG=(V,E)and integerk,determine if there is a subsetV0 Vwith|V0|ksuch that each edge inEis adjacent to a

34、 node inV0.12345678 1,3,4,6,7,8is a vertex cover,so is2,7,8.22Reduction from 3-SATCreate a pair of connected“literal”nodesxi,xifor each variablexi.Create a triangle for each clause,for a total ofmtriangles.For each clause(with 3 literals),connect the nodes of the appropriate triangle with thecorresp

35、onding literal nodes.Total nodes=2n+3m;total edges=6m+neach vertex cover n+2m;3-SAT is satisfiable iffa vertex cover of sizen+2m.23Some Other NP-complete ProblemsVertex Cover:Given graphG=(V,E)and integerk,determine if there is a subsetV0 Vwith|V0|ksuch that each edge inEis adjacent to a node inV0.M

36、ax Cut:Given graphG=(V,E)and integerk,determine if there exists a partitionV=V1 V2such that the number of edges going betweenV1andV2is at leastk.Knapsack problem:There is a knapsack of capacityc 0andNitems.Each itemhas valuevi 0and weightwi 0.Find the selection of items(i=1if selected,0if not)that f

37、it,PNi=1iwi c,and the total value,PNi=1ivi,is maximized.Partition:Given a cost matrixW SKand an integerk,determine if there exists apartitionV1 V2=1,2,.,Kwith a cost less thank.Here the total cost is thesum of all costs induced by each pair(i,j),withWijsignifying the cost ofiandjbelonging to the same set andWijotherwise.Nonconvex QP:minxTQx,subject toAx b.Minimizing a fourth order polynomial:Given a fourth order polynomialf(x),determine if there existsxR such thatf(x)0.24