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

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

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

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

fstrings.Instance:strings.AlgorithmAsolvesproblemX:A(s)=yesiffs∈X.Optimizationproblems.inwhicheachfeasible(i.e.,"legal")solut

ionhasanassociatedvalue,andwewishtofindthefeasiblesolutionwiththebestvalue.3Polynomialtime.AlgorithmArunsinpoly-timeifforeverystrings,A(s)termina

tesinatmostp(|s|)"steps",wherep(.)issomepolynomial.Certificationalgorithmintuition.Certifierviewsthingsfrom"managerial"viewpoint.C

ertifierdoesn'tdeterminewhethers∈Xonitsown;rather,itchecksaproposedcertificatetthats∈X.i.e.,certifierverifythe

proposedsolutiontandtheinstanceswhetherC(s,t)isyes.4Def.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,s∈Xiffthereexistsastring

tsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereexistsapoly-timecertifier.Remark.NPstandsfornondeterministicpoly-time

.5CertifiersandCertificates:Composite(合数)COMPOSITES.Givenanintegers,isscomposite?Certificate.Anontrivialfactortofs.Notethatsuchacertificateexistsif

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

437,669.Certificate.t=541or809.Conclusion.COMPOSITESisinNP.7CertifiersandCertificates:3-SatisfiabilitySAT.GivenaCNFformula

,isthereasatisfyingassignment?Certificate.Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Checkthateach

clauseinhasatleastonetrueliteral.123123124134()()()()xxxxxxxxxxxx12341,1,0,1xxxx====Instance:Certi

ficate:Conclusion.SATisinNP.8CertifiersandCertificates:HamiltonianCycleHAM-CYCLE.GivenanundirectedgraphG=(V,

E),doesthereexistasimplecycleCthatvisitseverynode?Certificate.Apermutationofthennodes.Certifier.Checkthatthepermutatio

ncontainseachnodeinVexactlyonce,andthatthereisanedgebetweeneachpairofadjacentnodesinthepermutation.Conclusion.HAM-CYCLEisinNP.9

P,NP,EXPP.Decisionproblemsforwhichthereisapoly-timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential-timealgorithm.NP.Decis

ionproblemsforwhichthereisapoly-timecertifier.10Claim.Pf.ConsideranyproblemXinP.Bydefinition,thereexistsapoly-timeal

gorithmA(s)thatsolvesX.Certificate:certifierC(s,t)=A(s).Claim.Pf.ConsideranyproblemXinNP.Bydefinition,t

hereexistsapoly-timecertifierC(s,t)forX.Tosolveinputs,runC(s,t)onallstringstwith|t|≤p(|s|).Returnyes,ifC(s,t)returns

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

]Isthedecisionproblemaseasyasthecertificationproblem?Clay$1millionprize.EXPNPPEXPP=NPIfP=NPIfP≠NP12Aformual-languageFrameworkAnalphabetΣisaf

initesetofsymbols.AlanguageLoverΣisanysetofstringsmadeupofsymbolsfromΣ.Forexample,Σ={0,1},L={10,11,101,111,1011,1101,10001,...}Listhelanguageofbin

aryrepresentationsofprimenumbersDenoteemptystringbyε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}.TheclosureorKleenestarofalanguageListhelanguageL*={ε}∪L∪L2∪L3∪·

··,whereLkisthelanguageobtainedbyconcatenatingLtoitselfktimes.15DecisionproblemandlanguagethesetofinstancesforanydecisionproblemQissimplyth

esetΣ*,whereΣ={0,1}.SinceQisentirelycharacterizedbythoseprobleminstancesthatproducea1(yes)answer,wecanviewQasalanguageLoverΣ={0,1

},whereL={x∈Σ*:Q(x)=1}.Example:PATH={〈G,u,v,k〉:G=(V,E)isanundirectedgraph,u,v∈V,k≥0isaninteger,andthereexists

apathfromutovinGconsistingofatmostkedges}.16WesaythatanalgorithmAacceptsastringx∈{0,1}*if,giveninputx,thealgorithm'soutputA(x)is1.Thela

nguageacceptedbyanalgorithmAisthesetofstringsL={x∈{0,1}*:A(x)=1}AnalgorithmArejectsastringxifA(x)=0.AlanguageLisdecidedbyanalgorithmAifeverybina

rystringinLisacceptedbyAandeverybinarystringnotinLisrejectedbyA.17AlanguageLisacceptedinpolynomialtimebyanalgorithmAifitisacceptedbyA

andifinadditionthereisaconstantksuchthatforanylength-nstringx∈L,algorithmAacceptsxintimeO(nk).AlanguageLisdecided

inpolynomialtimebyanalgorithmAifthereisaconstantksuchthatforanylength-nstringx∈{0,1}*,thealgorithmcorrectlydecideswhetherx∈Lint

imeO(nk).Toacceptalanguage,analgorithmneedonlyworryaboutstringsinL,buttodecidealanguage,itmustcorrectlyacceptor

rejecteverystringin{0,1}*.18ClassPP={L⊆{0,1}*:thereexistsanalgorithmAthatdecidesLinpolynomialtime}19Polyno

mial-timeverificationForexample,supposethatforagiveninstance〈G,u,v,k〉ofthedecisionproblemPATH,Wearealsogivenapathpfromutov.Wecaneasilycheckwhe

therthelengthofpisatmostk.So,wecanviewpasa"certificate"thattheinstanceindeedbelongstoPATH.20Verificationalgorithmsdefineaverificati

onalgorithmasbeingatwo-argumentalgorithmA,whereoneargumentisanordinaryinputstringxandtheotherisabinarystringycalledacertificate.Atwo

-argumentalgorithmAverifiesaninputstringxifthereexistsacertificateysuchthatA(x,y)=1.Thelanguageverified

byaverificationalgorithmAisL={x∈{0,1}*:thereexistsy∈{0,1}*suchthatA(x,y)=1}.21ClassNPThecomplexityclassNPistheclassoflanguagesthatcanbeverifi

edbyapolynomial-timealgorithmMoreprecisely,alanguageLbelongstoNPifandonlyifthereexistatwo-inputpolynomial-timealgorithmAandconstantcsuchthatL={x∈{0

,1}*:thereexistsacertificateywith|y|=O(|x|c)suchthatA(x,y)=1}.WesaythatalgorithmAverifieslanguageLinpolynomialtime.

22classco-NPThatis,doesL∈NPimplyWecandefinethecomplexityclassco-NPasthesetoflanguagesLsuchthat?LNPLNPP=N

P=co-NPNP=co-NPPco-NPP=NP∩co-NPNPco-NPNP∩co-NPNPP23NP-completenessandreducibilityPolynomialTransformationDef

.ProblemXpolynomialreduces(Cook)toproblemYifarbitraryinstancesofproblemXcanbesolvedusing:Polynomialnumberofstandardcomputational

steps,plusPolynomialnumberofcallstooraclethatsolvesproblemY.Def.ProblemXpolynomialtransforms(Karp)toproblemYifgiven

anyinputxtoX,wecanconstructaninputyinpolynomialtimesuchthatxisayesinstanceofXiffyisayesinstanceofY.24wesaythatal

anguageL1ispolynomial-timereducibletoalanguageL2writtenL1≤PL2,ifthereexistsapolynomial-timecomputablefunctionf:{0,1}*→{0,1}*suchthatforallx

{0,1}*,Wecallthefunctionfthereductionfunction,andapolynomial-timealgorithmFthatcomputesfiscalledareductionalgorithm

.12ifandonlyif()xLfxL25NP-CompleteNP-complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,X≤PY.Ala

nguageL⊆{0,1}*isNP-completeifL∈NP,andL′≤PLforeveryL∈NP.26Lemma.IfL1,L2⊆{0,1}*arelanguagessuchthatL1≤PL2,thenL2∈Pimplie

sL1∈P.FA2xf(x)2,()yesfxL1,yesxL2,()nofxL2,noxLA127Theorem.IfanyNP-completeproblemispolynomial-timesolvable,thenP=NP.Pf.Supposethat

L∈PandalsothatL∈NPC.ForanyL′∈NP,wehaveL′≤PLbyproperty2ofthedefinitionofNP-completeness.Thus,byaboveLemma,wealsohave

thatL′∈P,whichprovesthetheorem.NPPNPCIfP≠NP28CircuitSatisfiabilityCIRCUIT-SAT.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawayto

setthecircuitinputssothattheoutputis1?10???Yes:101Output29The"First"NP-CompleteProblemTheorem.CIRCUIT-SATisNP-complete.[

Cook1971,Levin1973]Pf.Thecircuit-satisfiabilityproblembelongstotheclassNP.showthateverylanguageinNPispolynomial-timere

ducibletoCIRCUIT-SAT.30EstablishingNP-CompletenessMethodforshowingthataproblemYisNP-completeShowthatYisinNP.ChooseanNP-completeproblemX.

X≤PYJustification.IfXisaproblemsuchthatY≤PXforsomeY∈NPC,thenXisNP-hard.Moreover,ifX∈NP,thenL∈NPC.313-SATisNP-CompleteTheo

rem.3-SATisNP-complete.Pf.SufficestoshowthatCIRCUIT-SAT≤P3-SATsince3-SATisinNP.LetKbeanycircuitCreatea3-SATvariablexiforeachcirc

uitelementi.x5x4x3x1x2x02323232,xxaddclausesxxxx=32Proof.Con.14514151453,,xxxaddclausesxxxxxxx=01201020123,,xxxaddclausesxxxxx

xx=550001xxxx==33Proof.Con.Finalstep:turnclausesoflength<3intoclausesoflengthexactly3!IfChas3distinctliter

als,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,orCNF,ifitisexpressedasanANDofc

lauses,eachofwhichistheORofoneormoreliterals.3-CNF,ifeachclausehasexactlythreedistinctliterals.Example:(x1∨¬x1∨¬x2)∧(x3

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

AcliqueinanundirectedgraphG=(V,E)isasubsetV'⊆Vofvertices,eachpairofwhichisconnectedbyanedgeinE.Inotherwords,acliqueisacomple

tesubgraphofG.Thesizeofacliqueisthenumberofverticesitcontains.Thecliqueproblemistheoptimizationproblemoffindingacliqueofmaxi

mumsizeinagraph.Asadecisionproblem,weasksimplywhetheracliqueofagivensizekexistsinthegraph.TheformaldefinitionisCLIQUE={〈G,k〉:Gis

agraphwithacliqueofsizek}.37CliqueproblemTheorem.ThecliqueproblemisNP-complete.Pf.CLIQUEisinNP,foragivengraphG=(V,E),weuset

hesetV'⊆VofverticesinthecliqueasacertificateforG.CheckingwhetherV'isacliquecanbeaccomplishedinpolynomialtimebycheckingwhether,fo

reachpairu,v∈V',theedge(u,v)belongstoE.nextprovethat3-CNF-SAT≤PCLIQUEreductionalgorithm:Letφ=C1∧C2∧···∧Ckbeabooleanformulain3-CNFwithkclaus

es.WeshallconstructagraphGsuchthatφissatisfiableifandonlyifGhasacliqueofsizek.38ConstructofgraphGThegraphG=(V,E)isconstructedasfollow

s.ForeachclauseCr=(r1,r2,r3),weplaceatripleofverticesvr1,vr2,vr3inV.Weputanedgebetweentwoverticesvri,vsjifbothofthefollowinghold

:vriandvsjareindifferenttriples,thatis,r≠s,theircorrespondingliteralsareconsistent,thatisriisnotthenegationofsj.Thisgraphcaneasilybe

computedfromφinpolynomialtime39Exampleφ=(x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)∧(x1∨x2∨x3),40Proof.Con.WemustshowthatthistransformationofφintoGisareductionFi

rst,supposethatφhasasatisfyingassignment.TheneachclauseCrcontainsatleastoneliteralrjthatisassigned1.andeac

hsuchliteralcorrespondstoavertexvrj.Pickingonesuch"true"literalfromeachclauseyieldsasetV'ofkvertices.Weclaimthat

V'isaclique.Foranytwoverticesvri,vsjwherer≠s,bothcorrespondingliteralsrirandsjaremappedto1bythegivensatisfyin

gassignment,andthustheliteralscannotbecomplements.41Proof.Con.Conversely,supposethatGhasacliqueV'ofsizek.Noedges

inGconnectverticesinthesametriple,andsoV'containsexactlyonevertexpertriple.Wecanassign1toeachliteralrisuchthatvrj∈V',t

henassigning1tobothaliteralanditscomplementcannothappen,sinceGcontainsnoedgesbetweeninconsistentliterals.Eachc

lauseissatisfied,andsoφissatisfiedAnyvariablesthatdonotcorrespondtoavertexinthecliquemaybesetarbitrarily42Thevertex-coverproblemAvertexcoverofa

nundirectedgraphG=(V,E)isasubsetV'⊆Vsuchthatif(u,v)∈E,thenu∈V'orv∈V'(orboth).AvertexcoverforGisasetofverticesthatcoversa

lltheedgesinE.Asadecisionproblem,wedefineVERTEX-COVER={〈G,k〉:graphGhasavertexcoverofsizek}.43Vertex-cove

risNPCTheorem.Thevertex-coverproblemisNP-complete.WefirstshowthatVERTEX-COVER∈NP.GivenagraphG=(V,E)andan

integerk.CertificateisthevertexcoverV'⊆Vitself.Theverificationalgorithmaffirmsthat|V'|=k,andthenitchecks,foreachedge(u,v)∈E,thatu∈V'orv∈V'.Thisve

rificationcanbeperformedstraightforwardlyinpolynomialtime.44Thevertex-coverproblemisNP-hardbyshowingthatCLIQUE≤PVERTEX-COVERTh

isreductionisbasedonthenotionofthe"complement"ofagraph.GivenanundirectedgraphG=(V,E),wedefinethecomplementofG,the

graphcontainingexactlythoseedgesthatarenotinG.45Example:complementofG46Vertex-coverThereductionalgorithmtakesasinputaninstance〈

G,k〉ofthecliqueproblem.Itcomputesthecomplement,whichiseasilydoneinpolynomialtime.Theoutputofthereductionalgorithmistheinstanceoft

hevertex-coverproblem.ThegraphGhasacliqueofsizekifandonlyifthegraphhasavertexcoverofsize|V|-k.,||GVk−GG47Vertex-cov

erSupposethatGhasacliqueV'⊆Vwith|V'|=k.WeclaimthatV-V'isavertexcoverin.Let(u,v)beanyedgeinĒ.Then,(u,v)∉E,whichimpliesthatatleastoneofuorvdoesnotbel

ongtoV',sinceeverypairofverticesinV'isconnectedbyanedgeofE.Equivalently,atleastoneofuorvisinV-V‘,whichmeansthatedge(u,v)iscoveredbyV-V'.Hence,th

esetV-V',whichhassize|V|-k,formsavertexcoverforGG48Vertex-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'isacliq

ue,andithassize|V|-|V'|=k.G49HamiltonianCycleHAM-CYCLE:givenanundirectedgraphG=(V,E),doesthereexistasimplecyclet

hatcontainseverynodeinV.YES:verticesandfacesofadodecahedron.50HamiltonianCycleHAM-CYCLE:givenanundirectedgraphG=(V,E),

doesthereexistasimplecyclethatcontainseverynodeinV.NO:bipartitegraphwithoddnumberofnodes..51DirectedHamiltonianCycleDIR-HAM-CYCLE:givenadigraph

G=(V,E),doesthereexistsasimpledirectedcyclethatcontainseverynodeinV?Claim.DIR-HAM-CYCLE≤PHAM-CYCLE.VV

inVoutV523-SATReducestoDirectedHamiltonianCycleClaim.3-SAT≤PDIR-HAM-CYCLE533-SATReducestoDirectedHamiltonianCycleClaim.3-SAT≤PDIR-HAM-CY

CLEPf.Givenaninstanceof3-SAT,weconstructaninstanceofDIRHAM-CYCLEthathasaHamiltoniancycleiffissatisfia

ble.Construction.First,creategraphthathas2nHamiltoniancycleswhichcorrespondinanaturalwayto2npossibletruthassignments.Intuition:traversepathif

romlefttorightiffsetvariablexi=1.54HamiltonianPathHAM-CYCLE≤pHAM-PATH:55LongestPathSHORTEST-PATH.Givenad

igraphG=(V,E),doesthereexistsasimplepathoflengthatmostkedges?LONGEST-PATH.GivenadigraphG=(V,E),doesthereexistsasimplepathoflengthatleastkedge

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

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

reisaHamiltoniancycle.Else,thereisnoHamiltoniancycle.57ThelongestpathIhavebeenhardworkingforsolong.Iswearit'sright,andhemarksi

twrong.SomehowI'llfeelsorrywhenit'sdone:GPA2.1IsmorethanIhopefor.Garey,Johnson,Karpandothermen(andwo

men)TriedtomakeitorderNlogN.AmIamadfoolIfIspendmylifeingradschool,Foreverfollowingthelongestpath?Woh-oh-oh-oh,findthelongest

path!Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelongestpath.Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelon

gestpath!IfyousaidPisNPtonight,Therewouldstillbepaperslefttowrite,Ihaveaweakness,I'maddictedtocompleteness,AndIkeepsearchingforthelongestpath.Thea

lgorithmIwouldliketoseeIsofpolynomialdegree,Butit'selusive:NobodyhasfoundconclusiveEvidencethatwecanfinda

longestpath.Lyrics.Copyright©1988byDanielJ.Barrett.Music.SungtothetuneofTheLongesttimebyBillyJoel.RecordedbyDanBarrettwhileagr

adstudentatJohnsHopkinsduringadifficultalgorithmsfinal.58Thetraveling-salesmanproblem(TSP)Traveling-salesmanproble

m:Asalesmanspendshistimevisitingncities(ornodes)cyclically.Inonetourhevisitseachcityjustonce,andfinishesup

wherehestarted.Inwhatordershouldhevisitthemtominimisethedistancetravelled?Thereisanintegercostc(i,j)totravelfromcityitocityj,59TSP:NPCTheor

em.Thetraveling-salesmanproblemisNP-complete.Pf.HAM-CYCLE≤PTSP.LetG=(V,E)beaninstanceofHAM-CYCLE.Wec

onstructaninstanceofTSPasfollows.WeformthecompletegraphG'=(V,E'),whereE'={(i,j):i,j∈Vandi≠j},andwedefinethecostfunctioncby0(,)(,)1ifijEC

ijelse=60Proof.graphGhasahamiltoniancycleifandonlyifgraphG'hasatourofcostatmost0.SupposethatgraphGhasahamiltoniancycleh.Eachedgeinhbelongs

toEandthushascost0inG'.Thus,hisatourinG'withcost0Conversely,supposethatgraphG'hasatourh'ofcostatmost0.Sincethecostsofth

eedgesinE'are0and1,thecostoftourh'isexactly0andeachedgeonthetourmusthavecost0.Therefore,h'containsonlyedgesinE.Weconcludethath'isahamiltoniancyclein

graphG.61NPProblems62AcompendiumofNPoptimizationproblemsEditors:PierluigiCrescenzi,andViggoKannSubeditors:MagnúsHalldórsson(retired)GraphTheor

y:CoveringandPartitioning,SubgraphsandSupergraphs,SetsandPartitions.MarekKarpinskiGraphTheory:VertexOrdering,NetworkDesign:CutsandC

onnectivity.GerhardWoegingerSequencingandScheduling.nada.kth.se/~viggo/problemlist/63TheNP-CompletenessColumnDa

vidJohnson.ACMTRANSACTIONSONALGORITHMS1:1,160-176(2019)64OpenProblemOpen:theVisibilityGraphRecognitionproblemisnotevenknowntobeinNP.Vis

ibilityGraphRecognitionproblem:GivenavisibilitygraphGandaHamiltoniancircuitC,determineinpolynomialtimewhetherthereisasimplepolygonwhosevertexvisibil

itygraphisG,andwhoseboundarycorrespondstoC.VisibilityGraph:LetSbeasetofsimplepolygonalobstaclesintheplane,thenthenodesofthevisibilitygraphofarejustth

everticesofS,andthereisanedge(calledavisibilityedge)betweenverticesandiftheseverticesaremutuallyvisible.Asimpl

epolygonisapolygonwhichdoesnotintersectitselfanywhere.ThesearealsocalledJordanpolygons.