算法设计与分析第15讲 NP问题

2008/06/13NP-completeness1資料結構與演算法(下)呂學一(Hsueh-ILu)~hil/2008/06/13NP-completeness2TodayPversusNPNP,NP-complete,NP-hardPolynomial-timereductionApproximationalgorithms2008/06/13NP-completeness3Part1PversusNP2008/06/13NP-completeness4MillenniumproblemsBirchandSwinnerton-DyerConjectureHodgeConjectureNavier-StokesEquationsPvsNPPoincaréConjectureRiemannHypothesisYang-MillsTheory2008/06/13NP-completeness5US$1,000,000perproblem1862~1943GermanmathematicianPresented23problemsin19002008/06/13NP-completeness7Hilbert’s23problems1.Cantor連續體的基數問題，2.算術公理的無矛盾性，3.等底等高兩四面體的等積性，4.兩點間最短路程做為直線的問題，5.連續群的定義函數除去可微性的問題6.物理學公理化，7.某些數的無理數性及超越性，8.質數問題，9.任何代數體中最一般的互逆法則，10.決定Diophantine方程式的可解性，11.係數為代數數的二次式，12.推廣Kronecker的Abel擴張定理到任何代數體上2008/06/13NP-completeness8Hilbert’s23problems13.七次方程式不能用兩變數函數來解，14.某些完備函數的有限性，15.Schubert算法的嚴密基礎，16.代數曲線與曲面的拓樸，17.正定型的平方和表現，18.以全等多面體鋪成空間的問題，19.正則變分問題的解都是解析的？20.一般的邊界值問題，21.給定Monodromy群，線性微分方程式的存在問題，22.以自我同構函數做解析關係的一致化，23.變分法的進一步開展。2008/06/13NP-completeness9KurtGodel1906~1978AustrianAmerican–mathematician–philosopherIncompletenesstheorems–25yearsold–Oneyearafterhisdoctoratedegree2008/06/13NP-completeness10MillenniumproblemsBirchandSwinnerton-DyerConjectureHodgeConjectureNavier-StokesEquationsPvsNPPoincaréConjectureRiemannHypothesisYang-MillsTheory2008/06/13NP-completeness11GrigoryPerelman1966~RussianmathematicianSolvedthePoincaréConjecturein2003Fieldsmedalist,2006–Declinedtoaccepttheaward2008/06/13NP-completeness12P=NP?2008/06/13NP-completeness13PTheclassPconsistsofalltheproblemsthatcanbesolvedinpolynomialtime.–Sorting–Exactstringmatching–Primes–…2008/06/13NP-completeness14NPNPconsistsoftheproblemsthatcanbesolvedinnon-deterministicallypolynomialtime.Pconsistsoftheproblemsthatcanbesolvedin(deterministically)polynomialtime.2008/06/13NP-completeness15DeterministicalgorithmInitialconfigurationInitialconfiguration2008/06/13NP-completeness16Non-deterministicalgorithmInitialconfigurationInitialconfiguration2008/06/13NP-completeness17Non-deterministicbubblesortfori=1ton–forj=1ton–1ifA[j]A[j+1]then–EitherexchangeA[j]andA[i+1]ordonothingThisisnotarandomizedalgorithm.2008/06/13NP-completeness18Non-deterministicallysolvingaproblemInitialconfigurationInitialconfigurationInitialconfigurationCorrectanswer2008/06/13NP-completeness19Non-deterministicallypolynomialtimeWesaythatanondeterministicalgorithmNrunsinpolynomialtimeifforanyinputxofN,anycompu-tationofNonxtakestimepolynomialinthesizeofx.polynomial2008/06/13NP-completeness20PversusNPFPµNPFAnyprobleminNPcanbesolvedin(deter-ministically)exponentialtime.(Why?)FCoulditbethecasethatanyprobleminNPcanalsobesolvedin(deterministically)poly-nomialtime?INobodyknows.Sofar,nobodycanproveordisproveit.IWhetherP=NPornotisTHEopenprob-lemin(Theoretical)ComputerScience.2008/06/13NP-completeness21Part2NP,NP-complete,NP-hard2008/06/13NP-completeness22Commonmistakes“NPstandsfornon-polynomialtime”.–Correctversion:“NPstandsfornon-deterministicpolynomialtime”“TravelingSalesmanProblemisanNPproblem,soitisaverydifficultproblem.”–Correctversion:TSPisanNP-complete(orNP-hard)problem,soitisaverydifficultproblem.2008/06/13NP-completeness23NP-hardnessAproblemisNP-hardifitisasleastashardasalltheproblemsinNP.Whatdoesitmean?2008/06/13NP-completeness24NP-hardnessMoreprecisely,aproblemXisNP-hardifthefollowingconditionholds:–IfXcanbesolvedin(deterministically)polynomialtime,thenalltheproblemsinNPcanbesolvedin(deterministically)polynomialtime.2008/06/13NP-completeness25NP-completenessAproblemisNP-completeif–itisNP-hardand–itisinNP.Inotherwords,aNP-completeproblemisa“hardest”probleminNP.ItisahardnessrepresentativeproblemoftheclassNP.2008/06/13NP-completeness26Question:IsthereanyNP-completeproblem?2008/06/13NP-completeness27StephenA.Cook1939~Ph.D.,HarvardUCBerkeleyCurrentlywith–UniversityofTorontoTuringAward,19822008/06/13NP-completeness28SAT(Satisfiability)Input:–Abooleanformulawithvariables,Output:–whetherthereisatruthassignmentforthevariablesthatsatisfiestheinputbooleanformula.Example:(x_y_¹z)^(¹x_z_w)^(x_w)2008/06/13NP-completeness29Cook’scontributionSATisthefirstknownNP-completeproblem.Cook[FOCS1971]provedthat–SATcanbesolvedinnon-deterministicallypolynomialtime.–IfSATcanbesolvedindeterministicallypolynomialtime,thensocananyNPproblems.2008/06/13NP-completeness30SAT:akeytoPversusNPIfoneprovesthatSATcanbesolvedbyapolynomial-timealgorithm,thenNP=P.IfsomebodyprovesthatSATcannotbesolvedbyanypolynomial-timealgorithm,thenNP≠P.2008/06/13NP-completeness31Part3Polynomial-timereduction2008/06/13NP-completeness32QuestionArethereotherNP-completeproblems?2008/06/13NP-completeness33RichardN.Karp1935~CurrentlywithUCBerkeleyTuringaward,19852008/06/13NP-completeness34Karp’s21NP-completeproblems1.CNF-SAT2.0-1INTEGERPROGRAMMING3.CLIQUE4.SETPACKING5.VERTEXCOVER6.SETCOVERING7.FEEDBACKARCSET8.FEEDBACKNODESET9.DIRECTEDHAMILTONIANCIRCUIT10.UNDIRECTEDHAMILTONIANCIRCUIT11.3-SA