【文档说明】-算法和程序设计-NP问题-精选.ppt，共(64)页，352.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2525.html

以下为本文档部分文字说明：

1NPandComputationalIntractability叶德仕yedeshigmail2DecisionProblemsDecisionproblem.(theanswerissimply"yes"or"no")Xis

asetofstrings.Instance:strings.AlgorithmAsolvesproblemX:A(s)=yesiffs∈X.Optimizationproblems.inwhiche

achfeasible(i.e.,"legal")solutionhasanassociatedvalue,andwewishtofindthefeasiblesolutionwiththebestvalue.3Polynom

ialtime.AlgorithmArunsinpoly-timeifforeverystrings,A(s)terminatesinatmostp(|s|)"steps",wherep(.)issome

polynomial.Certificationalgorithmintuition.Certifierviewsthingsfrom"managerial"viewpoint.Certifierdoes

n'tdeterminewhethers∈Xonitsown;rather,itchecksaproposedcertificatetthats∈X.i.e.,certifierverifytheproposedso

lutiontandtheinstanceswhetherC(s,t)isyes.4Def.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,s∈XiffthereexistsastringtsuchthatC(s,t)=yes.NP.

Decisionproblemsforwhichthereexistsapoly-timecertifier.Remark.NPstandsfornondeterministicpoly-time.5CertifiersandCertificates:Composite(合数)COMPOSIT

ES.Givenanintegers,isscomposite?Certificate.Anontrivialfactortofs.Notethatsuchacertificateexistsiffsiscom

posite.Moreover|t|≤|s|.Certifier.booleanC(s,t){if(t≤1ort≥s)returnfalseelseif(sisamultipleoft)returntrueelsereturnfalse}6ExampleIn

stance.s=437,669.Certificate.t=541or809.Conclusion.COMPOSITESisinNP.7CertifiersandCertificates:3-Satisfiabil

itySAT.GivenaCNFformula,isthereasatisfyingassignment?Certificate.Anassignmentoftruthvaluestothenbooleanvariables.Cer

tifier.Checkthateachclauseinhasatleastonetrueliteral.123123124134()()()()xxxxxxxxxxxx123

41,1,0,1xxxx====Instance:Certificate:Conclusion.SATisinNP.8CertifiersandCertificates:HamiltonianCycleHAM-CYCLE.Give

nanundirectedgraphG=(V,E),doesthereexistasimplecycleCthatvisitseverynode?Certificate.Apermutationofthennode

s.Certifier.CheckthatthepermutationcontainseachnodeinVexactlyonce,andthatthereisanedgebetweeneachpairofadjacentnodesinthepermutation.

Conclusion.HAM-CYCLEisinNP.9P,NP,EXPP.Decisionproblemsforwhichthereisapoly-timealgorithm.EXP.Decisionproblemsfor

whichthereisanexponential-timealgorithm.NP.Decisionproblemsforwhichthereisapoly-timecertifier.10Claim.Pf.Consi

deranyproblemXinP.Bydefinition,thereexistsapoly-timealgorithmA(s)thatsolvesX.Certificate:certifierC(s,t)=A(s).Claim.Pf.ConsideranyproblemXinNP.By

definition,thereexistsapoly-timecertifierC(s,t)forX.Tosolveinputs,runC(s,t)onallstringstwith|t|≤p(|s|).Returnyes,ifC(s,t)returnsyesforanyofthe

se.!PNPNPEXP11TheMainQuestion:PVersusNPDoesP=NP?[Cook1971,Edmonds,Levin,Yablonski,Gödel]Isthedecisionproblemas

easyasthecertificationproblem?Clay$1millionprize.EXPNPPEXPP=NPIfP=NPIfP≠NP12Aformual-languageFrameworkAnalphabetΣisafinitesetofsymbols.Alangua

geLoverΣisanysetofstringsmadeupofsymbolsfromΣ.Forexample,Σ={0,1},L={10,11,101,111,1011,1101,10001,...}Listhelanguageofbinaryrep

resentationsofprimenumbersDenoteemptystringbyεDenoteemptylanguagebyØ13ThelanguageofallstringsoverΣisdenotedΣ*.ForexampleΣ={

0,1},thenΣ*={ε,0,1,00,01,10,11,000,...}isthesetofallbinarystrings.EverylanguageLoverΣisasubsetofΣ*.14Set

-theoreticoperationscomplementofLbyΣ*-L.TheconcatenationoftwolanguagesL1andL2isthelanguageL={x1x2:x1∈L1andx2∈L2}.TheclosureorKleenesta

rofalanguageListhelanguageL*={ε}∪L∪L2∪L3∪···,whereLkisthelanguageobtainedbyconcatenatingLtoitselfktimes.15Decisionproblemandlanguagethesetofinstance

sforanydecisionproblemQissimplythesetΣ*,whereΣ={0,1}.SinceQisentirelycharacterizedbythoseprobleminstancesthat

producea1(yes)answer,wecanviewQasalanguageLoverΣ={0,1},whereL={x∈Σ*:Q(x)=1}.Example:PATH={〈G,u,v,k〉:G=(V,E)isanun

directedgraph,u,v∈V,k≥0isaninteger,andthereexistsapathfromutovinGconsistingofatmostkedges}.16WesaythatanalgorithmAacceptsastringx∈{0,1}

*if,giveninputx,thealgorithm'soutputA(x)is1.ThelanguageacceptedbyanalgorithmAisthesetofstringsL={x∈{0,1}*:A(x)=

1}AnalgorithmArejectsastringxifA(x)=0.AlanguageLisdecidedbyanalgorithmAifeverybinarystringinLisacceptedbyAandeverybinarystringnotinL

isrejectedbyA.17AlanguageLisacceptedinpolynomialtimebyanalgorithmAifitisacceptedbyAandifinadditionthereisaconstantksuc

hthatforanylength-nstringx∈L,algorithmAacceptsxintimeO(nk).AlanguageLisdecidedinpolynomialtimebyanalgorithmAifthe

reisaconstantksuchthatforanylength-nstringx∈{0,1}*,thealgorithmcorrectlydecideswhetherx∈LintimeO(nk).Toacceptalanguage,analgorithmneedo

nlyworryaboutstringsinL,buttodecidealanguage,itmustcorrectlyacceptorrejecteverystringin{0,1}*.18ClassPP={

L⊆{0,1}*:thereexistsanalgorithmAthatdecidesLinpolynomialtime}19Polynomial-timeverificationForexample,supposethatforagiveninstance〈G,u,v,k〉of

thedecisionproblemPATH,Wearealsogivenapathpfromutov.Wecaneasilycheckwhetherthelengthofpisatmostk.So,we

canviewpasa"certificate"thattheinstanceindeedbelongstoPATH.20Verificationalgorithmsdefineaverificationalgorithmasbeingatwo-argumentalgori

thmA,whereoneargumentisanordinaryinputstringxandtheotherisabinarystringycalledacertificate.Atwo-argumentalgorithmAverifiesaninputstringxifthereexists

acertificateysuchthatA(x,y)=1.ThelanguageverifiedbyaverificationalgorithmAisL={x∈{0,1}*:thereexistsy∈{0,1}*suchthatA(x,y)=1}.21Cl

assNPThecomplexityclassNPistheclassoflanguagesthatcanbeverifiedbyapolynomial-timealgorithmMoreprecisely,alanguageLb

elongstoNPifandonlyifthereexistatwo-inputpolynomial-timealgorithmAandconstantcsuchthatL={x∈{0,1}*:thereexistsacertificateywith|y|=O(|x|c)suchtha

tA(x,y)=1}.WesaythatalgorithmAverifieslanguageLinpolynomialtime.22classco-NPThatis,doesL∈NPimplyWecandefinethecomple

xityclassco-NPasthesetoflanguagesLsuchthat?LNPLNPP=NP=co-NPNP=co-NPPco-NPP=NP∩co-NPNPco-NPNP∩co-NPNPP23NP-completenessan

dreducibilityPolynomialTransformationDef.ProblemXpolynomialreduces(Cook)toproblemYifarbitraryinstancesofproblemXcanbesolvedusing:Polynomialnumberof

standardcomputationalsteps,plusPolynomialnumberofcallstooraclethatsolvesproblemY.Def.ProblemXpolynomialtransforms(Karp)toproblemYifgivenany

inputxtoX,wecanconstructaninputyinpolynomialtimesuchthatxisayesinstanceofXiffyisayesinstanceofY.24wesaythatalanguageL1ispolynomial-time

reducibletoalanguageL2writtenL1≤PL2,ifthereexistsapolynomial-timecomputablefunctionf:{0,1}*→{0,1}*suchthatforallx{0,1}*,Wecallthefunc

tionfthereductionfunction,andapolynomial-timealgorithmFthatcomputesfiscalledareductionalgorithm.12ifandonlyif()

xLfxL25NP-CompleteNP-complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,X≤PY.AlanguageL⊆{0,1}*isNP-completeifL∈NP,andL′≤PLforeveryL∈N

P.26Lemma.IfL1,L2⊆{0,1}*arelanguagessuchthatL1≤PL2,thenL2∈PimpliesL1∈P.FA2xf(x)2,()yesfxL1,yesxL2,()nofxL2,noxLA127Theorem.IfanyNP-completepro

blemispolynomial-timesolvable,thenP=NP.Pf.SupposethatL∈PandalsothatL∈NPC.ForanyL′∈NP,wehaveL′≤PLbyproperty2ofthedefinitionofNP-co

mpleteness.Thus,byaboveLemma,wealsohavethatL′∈P,whichprovesthetheorem.NPPNPCIfP≠NP28CircuitSatisfiabilityCIRCUIT-SA

T.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawaytosetthecircuitinputssothattheoutputis1?10???Yes:101Output29The"First"NP-Co

mpleteProblemTheorem.CIRCUIT-SATisNP-complete.[Cook1971,Levin1973]Pf.Thecircuit-satisfiabilityproblembelongstotheclassNP.showtha

teverylanguageinNPispolynomial-timereducibletoCIRCUIT-SAT.30EstablishingNP-CompletenessMethodforshowingthataproblemYisNP-completeShowthatYis

inNP.ChooseanNP-completeproblemX.X≤PYJustification.IfXisaproblemsuchthatY≤PXforsomeY∈NPC,thenXisNP-hard.Moreover,ifX∈NP,then

L∈NPC.313-SATisNP-CompleteTheorem.3-SATisNP-complete.Pf.SufficestoshowthatCIRCUIT-SAT≤P3-SATsince3-SATisinN

P.LetKbeanycircuitCreatea3-SATvariablexiforeachcircuitelementi.x5x4x3x1x2x02323232,xxaddclausesxxxx

=32Proof.Con.14514151453,,xxxaddclausesxxxxxxx=01201020123,,xxxaddclausesxxxxxxx=550001xxxx==33Proof.Con.Finalstep:turncl

ausesoflength<3intoclausesoflengthexactly3!IfChas3distinctliterals,done.IfChas2distinctliteralsifC=(L1∨L2),theninclude

(L1∨L2∨p)∧(L1∨L2∨¬p)IfChasjust1distinctliterall(l∨p∨q)∧(l∨p∨¬q)∧(l∨¬p∨q)∧(l∨¬p∨¬q)343-CNFsatisfiabilityAbooleanformulaisinconjunctivenormalform,orC

NF,ifitisexpressedasanANDofclauses,eachofwhichistheORofoneormoreliterals.3-CNF,ifeachclausehasexactlythreedistinctliterals.Example:(x1

∨¬x1∨¬x2)∧(x3∨x2∨x4)∧(¬x1∨¬x3∨¬x4)35Theorem.Satisfiabilityofbooleanformulasin3-conjunctivenormalformisNP-complete.36ThecliqueproblemAcliqueinanundir

ectedgraphG=(V,E)isasubsetV'⊆Vofvertices,eachpairofwhichisconnectedbyanedgeinE.Inotherwords,acliqueisacompletesubgraphofG.Thesizeofacliqueis

thenumberofverticesitcontains.Thecliqueproblemistheoptimizationproblemoffindingacliqueofmaximumsizeinagraph.Asadecisionproblem,weasksimplywhethe

racliqueofagivensizekexistsinthegraph.TheformaldefinitionisCLIQUE={〈G,k〉:Gisagraphwithacliqueofsizek}.37CliqueproblemTheorem.Thecliqueproblemis

NP-complete.Pf.CLIQUEisinNP,foragivengraphG=(V,E),weusethesetV'⊆VofverticesinthecliqueasacertificateforG.Checkin

gwhetherV'isacliquecanbeaccomplishedinpolynomialtimebycheckingwhether,foreachpairu,v∈V',theedge(u,v)belongstoE.nextprovethat3-CNF-SA

T≤PCLIQUEreductionalgorithm:Letφ=C1∧C2∧···∧Ckbeabooleanformulain3-CNFwithkclauses.WeshallconstructagraphGsuchthatφis

satisfiableifandonlyifGhasacliqueofsizek.38ConstructofgraphGThegraphG=(V,E)isconstructedasfollows.ForeachclauseCr=(r1,r2,

r3),weplaceatripleofverticesvr1,vr2,vr3inV.Weputanedgebetweentwoverticesvri,vsjifbothofthefollowinghold:vr

iandvsjareindifferenttriples,thatis,r≠s,theircorrespondingliteralsareconsistent,thatisriisnotthenegationofsj.Thisgraphcaneasilybecomputedfromφin

polynomialtime39Exampleφ=(x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)∧(x1∨x2∨x3),40Proof.Con.Wemustshowthatthistransform

ationofφintoGisareductionFirst,supposethatφhasasatisfyingassignment.TheneachclauseCrcontainsatleastoneliteralrjthatisassigned1.andeachs

uchliteralcorrespondstoavertexvrj.Pickingonesuch"true"literalfromeachclauseyieldsasetV'ofkvertices.Weclaimt

hatV'isaclique.Foranytwoverticesvri,vsjwherer≠s,bothcorrespondingliteralsrirandsjaremappedto1bythegivensatisfyingassignment,andthusthelitera

lscannotbecomplements.41Proof.Con.Conversely,supposethatGhasacliqueV'ofsizek.NoedgesinGconnectverticesinthesametripl

e,andsoV'containsexactlyonevertexpertriple.Wecanassign1toeachliteralrisuchthatvrj∈V',thenassigning1tobothaliteralanditscomplemen

tcannothappen,sinceGcontainsnoedgesbetweeninconsistentliterals.Eachclauseissatisfied,andsoφissatisfiedAn

yvariablesthatdonotcorrespondtoavertexinthecliquemaybesetarbitrarily42Thevertex-coverproblemAvertexcoverofanundirectedgraphG=(V,E)isasubse

tV'⊆Vsuchthatif(u,v)∈E,thenu∈V'orv∈V'(orboth).AvertexcoverforGisasetofverticesthatcoversalltheedgesinE.Asadecisionproblem,wedefineVERTEX-C

OVER={〈G,k〉:graphGhasavertexcoverofsizek}.43Vertex-coverisNPCTheorem.Thevertex-coverproblemisNP-complete.Wefirstshowtha

tVERTEX-COVER∈NP.GivenagraphG=(V,E)andanintegerk.CertificateisthevertexcoverV'⊆Vitself.Theverificationalgo

rithmaffirmsthat|V'|=k,andthenitchecks,foreachedge(u,v)∈E,thatu∈V'orv∈V'.Thisverificationcanbeperformedstraightforwardlyinpolynomial

time.44Thevertex-coverproblemisNP-hardbyshowingthatCLIQUE≤PVERTEX-COVERThisreductionisbasedonthenotionofthe"complement"

ofagraph.GivenanundirectedgraphG=(V,E),wedefinethecomplementofG,thegraphcontainingexactlythoseedgesthatarenotinG.45E

xample:complementofG46Vertex-coverThereductionalgorithmtakesasinputaninstance〈G,k〉ofthecliqueproblem.Itcomputesthecomplement,whichiseasily

doneinpolynomialtime.Theoutputofthereductionalgorithmistheinstanceofthevertex-coverproblem.ThegraphGhasacliqu

eofsizekifandonlyifthegraphhasavertexcoverofsize|V|-k.,||GVk−GG47Vertex-coverSupposethatGhasacliqueV'⊆Vwith|V'|=k.WeclaimthatV-V'

isavertexcoverin.Let(u,v)beanyedgeinĒ.Then,(u,v)∉E,whichimpliesthatatleastoneofuorvdoesnotbelongtoV',sinceeverypairofverticesinV'isconnectedbyan

edgeofE.Equivalently,atleastoneofuorvisinV-V‘,whichmeansthatedge(u,v)iscoveredbyV-V'.Hence,thesetV-V',whichhassize|V|-k,f

ormsavertexcoverforGG48Vertex-covercon.Conversely,supposethathasavertexcoverV'⊆V,where|V'|=|V|-k.Then,forallu,v∈V,if(

u,v)∈Ē,thenu∈V'orv∈V'orboth.Forallu,v∈V,ifu∉V'andv∉V',then(u,v)∈E.Inotherword,V-V'isaclique,andithassize|V|-|V'|=k.G49HamiltonianCycleHAM-CYC

LE:givenanundirectedgraphG=(V,E),doesthereexistasimplecyclethatcontainseverynodeinV.YES:verticesandfacesofadodecahedr

on.50HamiltonianCycleHAM-CYCLE:givenanundirectedgraphG=(V,E),doesthereexistasimplecyclethatcontainseverynodeinV.NO:bipartitegraphwithoddnum

berofnodes..51DirectedHamiltonianCycleDIR-HAM-CYCLE:givenadigraphG=(V,E),doesthereexistsasimpledirectedcyclethatcontainseverynodeinV?Cla

im.DIR-HAM-CYCLE≤PHAM-CYCLE.VVinVoutV523-SATReducestoDirectedHamiltonianCycleClaim.3-SAT≤PDIR-HAM-CYCLE533-SATReducestoDirectedHamiltonianCycle

Claim.3-SAT≤PDIR-HAM-CYCLEPf.Givenaninstanceof3-SAT,weconstructaninstanceofDIRHAM-CYCLEthathasaHamiltoniancycleiffissatisfiable.Constru

ction.First,creategraphthathas2nHamiltoniancycleswhichcorrespondinanaturalwayto2npossibletruthassignments.Intuition:traversepathifromlefttor

ightiffsetvariablexi=1.54HamiltonianPathHAM-CYCLE≤pHAM-PATH:55LongestPathSHORTEST-PATH.GivenadigraphG=(V,E),doesthereexistsasimple

pathoflengthatmostkedges?LONGEST-PATH.GivenadigraphG=(V,E),doesthereexistsasimplepathoflengthatleastk

edges?56LongestPathClaim.HAM-CYCLE≤pLongest-PathLetG=(V,E)beaninstanceofHAM-CYCLE.Ifthelongest-simple-cycleinGisoflength|V|,

theneveryvertexwasvisitedandthusthereisaHamiltoniancycleinG.Reduction:Computethelongest-simple-cycleinG.Ifthelengthofthiscycle=|V|,

ThereisaHamiltoniancycle.Else,thereisnoHamiltoniancycle.57ThelongestpathIhavebeenhardworkingforsolong.Iswearit'sright,andhemarksitwr

ong.SomehowI'llfeelsorrywhenit'sdone:GPA2.1IsmorethanIhopefor.Garey,Johnson,Karpandothermen(andwomen)Triedtomakei

torderNlogN.AmIamadfoolIfIspendmylifeingradschool,Foreverfollowingthelongestpath?Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelongestpa

th!Woh-oh-oh-oh,findthelongestpath.Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelongestpath!Ifyo

usaidPisNPtonight,Therewouldstillbepaperslefttowrite,Ihaveaweakness,I'maddictedtocompleteness,AndIkeepsearchingforthelongestpath.Thealgorit

hmIwouldliketoseeIsofpolynomialdegree,Butit'selusive:NobodyhasfoundconclusiveEvidencethatwecanfindalongestpath.Lyrics.Copyright©1988byDanielJ.Barrett

.Music.SungtothetuneofTheLongesttimebyBillyJoel.RecordedbyDanBarrettwhileagradstudentatJohnsHopkinsduringadifficultalgorith

msfinal.58Thetraveling-salesmanproblem(TSP)Traveling-salesmanproblem:Asalesmanspendshistimevisitingncities(ornodes)cyc

lically.Inonetourhevisitseachcityjustonce,andfinishesupwherehestarted.Inwhatordershouldhevisitthemtominimi

sethedistancetravelled?Thereisanintegercostc(i,j)totravelfromcityitocityj,59TSP:NPCTheorem.Thetravelin

g-salesmanproblemisNP-complete.Pf.HAM-CYCLE≤PTSP.LetG=(V,E)beaninstanceofHAM-CYCLE.Weconstructaninstanceo

fTSPasfollows.WeformthecompletegraphG'=(V,E'),whereE'={(i,j):i,j∈Vandi≠j},andwedefinethecostfunctioncby0(,)(,)1ifijECijelse=60Proof.graphGhas

ahamiltoniancycleifandonlyifgraphG'hasatourofcostatmost0.SupposethatgraphGhasahamiltoniancycleh.EachedgeinhbelongstoEandthushascost0inG'.Thus,hisatou

rinG'withcost0Conversely,supposethatgraphG'hasatourh'ofcostatmost0.SincethecostsoftheedgesinE'are0and1,thecostoftourh'ise

xactly0andeachedgeonthetourmusthavecost0.Therefore,h'containsonlyedgesinE.Weconcludethath'isahamiltoniancycleingrap

hG.61NPProblems62AcompendiumofNPoptimizationproblemsEditors:PierluigiCrescenzi,andViggoKannSubeditors:MagnúsHalldórsson(retired)GraphTheory:Co

veringandPartitioning,SubgraphsandSupergraphs,SetsandPartitions.MarekKarpinskiGraphTheory:VertexOrdering,NetworkDesign:CutsandConn

ectivity.GerhardWoegingerSequencingandScheduling.nada.kth.se/~viggo/problemlist/63TheNP-CompletenessCo

lumnDavidJohnson.ACMTRANSACTIONSONALGORITHMS1:1,160-176(2019)64OpenProblemOpen:theVisibilityGraphRecogn

itionproblemisnotevenknowntobeinNP.VisibilityGraphRecognitionproblem:GivenavisibilitygraphGandaHamiltoniancircuitC,determineinpo

lynomialtimewhetherthereisasimplepolygonwhosevertexvisibilitygraphisG,andwhoseboundarycorrespondstoC.VisibilityGraph:LetSbease

tofsimplepolygonalobstaclesintheplane,thenthenodesofthevisibilitygraphofarejusttheverticesofS,andthereis

anedge(calledavisibilityedge)betweenverticesandiftheseverticesaremutuallyvisible.Asimplepolygonisapol

ygonwhichdoesnotintersectitselfanywhere.ThesearealsocalledJordanpolygons.