-算法和程序设计-NP问题-课件

NPandComputational

Intractability叶德仕yedeshigmail1NPandComputational

Intractab

DecisionProblemsDecisionproblem.(theanswerissimply"yes"or"no")

Xisasetofstrings.Instance:strings.AlgorithmAsolvesproblemX:A(s)=yesiffs∈X.Optimizationproblems.inwhicheachfeasible(i.e.,"legal")solutionhasanassociatedvalue,andwewishtofindthefeasiblesolutionwiththebestvalue.2DecisionProblemsDecisioPolynomialtime.AlgorithmArunsinpoly-timeifforeverystrings,A(s)terminatesinatmostp(|s|)"steps",wherep(.)issomepolynomial.Certificationalgorithmintuition.Certifierviewsthingsfrom"managerial"viewpoint.Certifierdoesn'tdeterminewhethers∈Xonitsown;rather,itchecksaproposedcertificatetthats∈X.i.e.,certifierverifytheproposedsolutiontandtheinstanceswhetherC(s,t)isyes.3Polynomialtime.AlgorithmArDef.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,s∈XiffthereexistsastringtsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereexistsapoly-timecertifier.Remark.

NPstandsfornondeterministicpoly-time.4Def.AlgorithmC(s,t)isaceCertifiersandCertificates:

Composite(合数)COMPOSITES.Givenanintegers,isscomposite?Certificate.Anontrivialfactortofs.Notethatsuchacertificate

existsiffsiscomposite.Moreover|t|≤|s|.Certifier.booleanC(s,t){if(t≤1ort≥s)

returnfalseelseif(sisamultipleoft)

returntrueelse

returnfalse}5CertifiersandCertificateExampleInstance.

s=437,669.Certificate.

t=541or809.Conclusion.

COMPOSITESisinNP.6ExampleInstance.s=437,66

CertifiersandCertificates:

3-SatisfiabilitySAT.GivenaCNFformula,isthereasatisfyingassignment?Certificate.

Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Checkthateachclausein

hasatleastonetrueliteral.

Instance:Certificate:Conclusion.

SATisinNP.7CertifiersandCertificat

CertifiersandCertificates:

HamiltonianCycleHAM-CYCLE.GivenanundirectedgraphG=(V,E),doesthereexista

simplecycleCthatvisitseverynode?Certificate.Apermutationofthennodes.Certifier.CheckthatthepermutationcontainseachnodeinVexactly

once,andthatthereisanedgebetweeneachpairofadjacentnodesin

thepermutation.Conclusion.HAM-CYCLEisinNP.8CertifiersandCertifiP,NP,EXPP.Decisionproblemsforwhichthereisapoly-timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential-timealgorithm.NP.Decisionproblemsforwhichthereisapoly-timecertifier.9P,NP,EXPP.DecisionproblemsClaim.

Pf.ConsideranyproblemXinP.

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

Pf.ConsideranyproblemXinNP.Bydefinition,thereexistsapoly-timecertifierC(s,t)forX.

Tosolveinputs,runC(s,t)onallstringstwith|t|≤p(|s|).Returnyes,ifC(s,t)returnsyesforanyofthese.!10Claim.10TheMainQuestion:

PVersusNPDoesP=NP?[Cook1971,Edmonds,Levin,Yablonski,Gödel]Isthedecisionproblemaseasyasthecertificationproblem?Clay$1millionprize.EXPNPPEXPP=NPIfP=NPIfP≠NP11TheMainQuestion:

PVersusNAformual-language

FrameworkAnalphabet

Σisafinitesetofsymbols.Alanguage

LoverΣisanysetofstringsmadeupofsymbolsfromΣ.Forexample,Σ={0,1},

L={10,11,101,111,1011,1101,10001,...}ListhelanguageofbinaryrepresentationsofprimenumbersDenote

empty

stringbyε

Denote

empty

languagebyØ12Aformual-language

FrameworkAThelanguageofallstringsoverΣisdenotedΣ*.

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

13ThelanguageofallstringsovSet-theoretic

operationscomplementofLbyΣ*-L.

TheconcatenationoftwolanguagesL1andL2isthelanguageL={x1x2:x1∈L1andx2∈L2}.TheclosureorKleenestarofalanguageListhelanguageL*={ε}∪L∪L2∪L3∪···,whereLkisthelanguageobtainedbyconcatenatingLtoitselfktimes.14Set-theoretic

operationscompDecisionproblem

andlanguagethesetofinstancesforanydecisionproblemQissimplythesetΣ*,whereΣ={0,1}.

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

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

andlanguageWesaythatanalgorithmA

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

rejectsastringxifA(x)=0.AlanguageLisdecidedbyanalgorithmAifeverybinarystringin

LisacceptedbyAandeverybinarystringnotinLisrejectedbyA.

16WesaythatanalgorithmAaccAlanguageLisacceptedinpolynomialtimebyanalgorithmAifitisacceptedbyAandifinadditionthereisaconstantksuchthatforanylength-nstringx∈L,algorithmAacceptsxintimeO(nk).

AlanguageLisdecidedinpolynomialtimebyanalgorithmAifthereisaconstantksuchthatforanylength-nstringx∈{0,1}*,thealgorithmcorrectlydecideswhetherx∈LintimeO(nk).

Toacceptalanguage,analgorithmneedonlyworryaboutstringsinL,buttodecidealanguage,itmustcorrectlyacceptorrejecteverystringin{0,1}*.17AlanguageLisacceptedinpoClassPP={L⊆{0,1}*:thereexistsanalgorithmAthatdecides

Linpolynomialtime}

18ClassPP={L⊆{0,1}*:therPolynomial-time

verificationForexample,supposethatforagiveninstance〈G,u,v,k〉ofthedecisionproblemPATH,Wearealsogivenapathpfromutov.

Wecaneasilycheckwhetherthelengthofpisatmostk.So,wecanviewpasa"certificate"thattheinstanceindeedbelongstoPATH.19Polynomial-time

verificationVerificationalgorithmsdefineaverificationalgorithmasbeingatwo-argumentalgorithmA,whereoneargumentisanordinaryinputstringxandtheotherisabinarystringycalledacertificate.

Atwo-argumentalgorithmA

verifiesaninputstringxifthereexistsacertificateysuchthatA(x,y)=1.ThelanguageverifiedbyaverificationalgorithmAisL={x∈{0,1}*:thereexistsy∈{0,1}*suchthatA(x,y)=1}.20VerificationalgorithmsClassNPThecomplexityclass

NPistheclassoflanguagesthatcanbeverifiedbyapolynomial-timealgorithmMoreprecisely,alanguageLbelongstoNPifandonlyifthereexistatwo-inputpolynomial-timealgorithmAandconstantcsuchthatL={x∈{0,1}*:thereexistsacertificateywith|y|=O(|x|c)suchthatA(x,y)=1}.WesaythatalgorithmA

verifieslanguageL

inpolynomialtime.

21ClassNPThecomplexityclassNclassco-NPThatis,doesL∈NPimplyWecandefinethecomplexityclass

co-NPasthesetoflanguagesLsuchthatP=NP=co-NPNP=co-NPPco-NPP=NP∩co-NPNPco-NPNP∩co-NPNPP22classco-NPThatis,doesL∈NP-completeness

andreducibilityPolynomialTransformationDef.ProblemX

polynomialreduces(Cook)toproblemYifarbitraryinstancesofproblemXcanbesolvedusing:Polynomialnumberofstandardcomputationalsteps,plusPolynomialnumberofcallstooraclethatsolvesproblemY.Def.ProblemX

polynomialtransforms(Karp)toproblemYifgivenanyinputxtoX,wecanconstructaninputyinpolynomialtimesuchthatxisayesinstanceofXiffyisayesinstanceofY.23NP-completeness

andreducibilwesaythatalanguageL1

ispolynomial-timereducibletoalanguageL2

writtenL1≤P

L2,ifthereexistsapolynomial-timecomputablefunctionf:{0,1}*→{0,1}*suchthatforallx{0,1}*,Wecallthefunctionfthereductionfunction,andapolynomial-timealgorithmFthatcomputesfiscalledareductionalgorithm.24wesaythatalanguageL1ispNP-CompleteNP-complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,X≤PY.AlanguageL⊆{0,1}*isNP-completeifL∈NP,andL′≤P

LforeveryL∈NP.25NP-CompleteNP-complete.AprobLemma.IfL1,L2⊆{0,1}*arelanguagessuchthatL1≤P

L2,thenL2∈PimpliesL1∈P.FA2xf(x)A126Lemma.IfL1,L2⊆{0,1}*areTheorem.IfanyNP-completeproblemispolynomial-timesolvable,thenP=NP.Pf.SupposethatL∈PandalsothatL∈NPC.ForanyL′∈NP,wehaveL′≤P

Lbyproperty2ofthedefinitionofNP-completeness.Thus,byaboveLemma,wealsohavethatL′∈P,whichprovesthetheorem.NPPNPCIfP≠NP27Theorem.IfanyNP-completeprCircuitSatisfiabilityCIRCUIT-SAT.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawaytosetthecircuitinputssothattheoutputis1?10???Yes:101Output28CircuitSatisfiabilityCIRCUITThe"First"

NP-CompleteProblemTheorem.CIRCUIT-SATisNP-complete.[Cook1971,Levin1973]Pf.Thecircuit-satisfiabilityproblembelongstotheclassNP.showthateverylanguageinNPispolynomial-timereducibletoCIRCUIT-SAT.29The"First"

NP-CompleteProblEstablishingNP-CompletenessMethodforshowingthataproblemYisNP-completeShowthatYisinNP.ChooseanNP-completeproblemX.X≤P

Y

Justification.IfX

isaproblemsuchthatY

≤P

XforsomeY∈NPC,thenXisNP-hard.Moreover,ifX∈NP,thenL∈NPC.30EstablishingNP-3-SATisNP-CompleteTheorem.3-SATisNP-complete.Pf.SufficestoshowthatCIRCUIT-SAT≤P3-SATsince3-SATisinNP.LetKbeanycircuitCreatea3-SATvariablexiforeachcircuitelementi.x5x4x3x1x2x0313-SATisNP-CompleteThProof.Con.32Proof.Con.32Proof.Con.Finalstep:turnclausesoflength<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)

33Proof.Con.Finalstep:turncl3-CNFsatisfiabilityAbooleanformulaisinconjunctivenormalform,orCNF,ifitisexpressedasanANDofclauses,eachofwhichistheORofoneormoreliterals.

3-CNF,ifeachclausehasexactlythreedistinctliterals.

Example:(x1∨¬x1∨¬x2)∧(x3∨x2∨x4)∧(¬x1∨¬x3∨¬x4)343-CNFsatisfiabilityAbooleaTheorem.Satisfiabilityofbooleanformulasin3-conjunctivenormalformisNP-complete.35Theorem.SatisfiabilityofbooThecliqueproblemAcliqueinanundirectedgraphG=(V,E)isasubsetV'⊆Vofvertices,eachpairofwhichisconnectedbyanedgeinE.Inotherwords,acliqueisacompletesubgraphofG.Thesizeofacliqueisthenumberofverticesitcontains.Thecliqueproblemistheoptimizationproblemoffindingacliqueofmaximumsizeinagraph.Asadecisionproblem,weasksimplywhetheracliqueofagivensizekexistsinthegraph.Theformaldefinitionis

CLIQUE={〈G,k〉:Gisagraphwithacliqueofsizek}.36ThecliqueproblemAcliqueiCliqueproblemTheorem.ThecliqueproblemisNP-complete.Pf.CLIQUEisinNP,

foragivengraphG=(V,E),weusethesetV'⊆VofverticesinthecliqueasacertificateforG.CheckingwhetherV'isacliquecanbeaccomplishedinpolynomialtimebycheckingwhether,foreachpairu,v∈V',theedge(u,v)belongstoE.

nextprovethat3-CNF-SAT≤PCLIQUEreductionalgorithm:Letφ=C1∧C2∧···∧Ckbeabooleanformulain3-CNFwithkclauses.

WeshallconstructagraphGsuchthatφissatisfiableifandonlyifGhasacliqueofsizek.

37CliqueproblemTheorem.ThecliConstructofgraphGThegraphG=(V,E)isconstructedasfollows.ForeachclauseCr=(r1,r2,r3),weplaceatripleofverticesvr1,vr2,vr3inV.Weputanedgebetweentwovertices

vri,vsj

ifbothofthefollowinghold:

vri

andvsj

areindifferenttriples,thatis,r≠s,theircorrespondingliteralsareconsistent,thatisriisnotthenegationofsj.Thisgraphcaneasilybecomputedfromφinpolynomialtime38ConstructofgraphGThegraphExampleφ=(x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)∧(x1∨x2∨x3),

39Exampleφ=(x1∨¬x2∨¬x3)∧Proof.Con.WemustshowthatthistransformationofφintoGisareduction

First,supposethatφhasasatisfyingassignment.TheneachclauseCrcontainsatleastoneliteralrjthatisassigned1.andeachsuchliteralcorrespondstoavertexvrj.Pickingonesuch"true"literalfromeachclauseyieldsasetV'ofkvertices.

WeclaimthatV'isaclique.

Foranytwovertices

vri,vsj

wherer≠s,bothcorrespondingliteralsrirandsjaremappedto1bythegivensatisfyingassignment,andthustheliteralscannotbecomplements.40Proof.Con.WemustshowthattProof.Con.Conversely,supposethatGhasacliqueV'ofsizek.

NoedgesinGconnectverticesinthesametriple,andsoV'containsexactlyonevertexpertriple.Wecanassign1toeachliteral

risuchthatvrj∈V',thenassigning1tobothaliteralanditscomplement

cannothappen,sinceGcontainsnoedgesbetweeninconsistentliterals.Eachclauseissatisfied,andsoφissatisfiedAnyvariablesthatdonotcorrespondtoavertexinthecliquemaybesetarbitrarily

41Proof.Con.Conversely,supposeThevertex-coverproblemAvertexcoverofanundirectedgraphG=(V,E)isasubsetV'⊆Vsuchthatif(u,v)∈E,thenu∈V'orv∈V'(orboth).

AvertexcoverforGisasetofverticesthatcoversalltheedgesinE.Asadecisionproblem,wedefineVERTEX-COVER={〈G,k〉:graphGhasavertexcoverofsizek}.42Thevertex-coveVertex-coverisNPCTheorem.Thevertex-coverproblemisNP-complete.WefirstshowthatVERTEX-COVER∈NP.GivenagraphG=(V,E)andanintegerk.CertificateisthevertexcoverV'⊆Vitself.Theverificationalgorithmaffirmsthat|V'|=k,andthenitchecks,foreachedge(u,v)∈E,thatu∈V'orv∈V'.Thisverificationcanbeperformedstraightforwardlyinpolynomialtime.43Vertex-coverisNPCThThevertex-coverproblemisNP-hardbyshowingthatCLIQUE≤PVERTEX-COVER

Thisreductionisbasedonthenotionofthe"complement"ofagraph.GivenanundirectedgraphG=(V,E),wedefinethecomplementofG,thegraphcontainingexactlythoseedgesthatarenotinG.44Thevertex-coverproblemisNPExample:

complementofG45Example:

complementofG45Vertex-coverThereductionalgorithmtakesasinputaninstance〈G,k〉ofthecliqueproblem.Itcomputesthecomplement,whichiseasilydoneinpolynomialtime.Theoutputofthereductionalgorithmistheinstanceofthevertex-coverproblem.ThegraphGhasacliqueofsizek

ifandonlyifthegraphhasavertexcoverofsize|V|-k.46Vertex-coverThereductionalgoVertex-coverSupposethatGhasacliqueV'⊆Vwith|V'|=k.WeclaimthatV-V'isavertexcoverin.Let(u,v)beanyedgeinĒ.Then,(u,v)∉E,whichimpliesthatatleastoneofuorvdoesnotbelongtoV',sinceeverypairofverticesinV'isconnectedbyanedgeofE.Equivalently,atleastoneofuorvisinV-V‘,whichmeansthatedge(u,v)iscoveredbyV-V'.Hence,thesetV-V',whichhassize|V|-k,formsavertexcoverfor47Vertex-coverSupposethatGhasVertex-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.48Vertex-covercon.Conversely,sHamiltonianCycleHAM-CYCLE:givenanundirectedgraphG=(V,E),doesthereexistasimplecyclethatcontainseverynodeinV.YES:verticesandfacesofadodecahedron.49HamiltonianCycleHAM-CYCLE:giHamiltonianCycleHAM-CYCLE:givenanundirectedgraphG=(V,E),doesthereexistasimplecyclethatcontainseverynodeinV.NO:bipartitegraphwithoddnumberofnodes..50HamiltonianCycleHAM-CYCLE:giDirected

HamiltonianCycleDIR-HAM-CYCLE:givenadigraphG=(V,E),doesthereexistsasimpledirectedcyclethatcontainseverynodeinV?Claim.DIR-HAM-CYCLE≤PHAM-CYCLE.VVinVoutV51Directed

HamiltonianCycleDIR3-SATReducesto

DirectedHamiltonianCycle

Claim.3-SAT

≤PDIR-HAM-CYCLE523-SATReducesto

Di3-SATReducesto

DirectedHamiltonianCycle

Claim.3-SAT

≤PDIR-HAM-CYCLEPf.Givenaninstanceof3-SAT,weconstructaninstanceofDIRHAM-CYCLEthathasaHamiltoniancycleiffissatisfiable.Construction.First,creategraphthathas2n

Hamiltoniancycleswhichcorrespondinanaturalwayto2npossibletruthassignments.Intuition:traversepathifromlefttorightiffsetvariablexi=1.533-SATReducesto

DiHamiltonianPathHAM-CYCLE≤pHAM-PATH:54HamiltonianPathHAM-CYCLE≤pHLongestPathSHORTEST-PATH.GivenadigraphG=(V,E),doesthereexistsasimplepathoflengthatmostkedges?LONGEST-PATH.GivenadigraphG=(V,E),doesthereexistsasimplepathoflengthatleastkedges?55LongestPathSHORTEST-PATH.GivLongestPathClaim.HAM-CYCLE≤pLongest-PathLetG=(V,E)beaninstanceofHAM-CYCLE.Ifthelongest-simple-cycleinGisoflength|V|,theneveryvertexwasvisitedandthusthereisaHamiltoniancycleinG.Reduction:Computethelongest-simple-cycleinG.Ifthelengthofthiscycle=|V|,ThereisaHamiltoniancycle.Else,thereisnoHamiltoniancycle.56LongestPathClaim.HAM-CYCLE≤ThelongestpathIhavebeenhardworkingforsolong.Iswearit'sright,andhemarksitwrong.SomehowI'llfeelsorrywhenit'sdone:GPA2.1IsmorethanIhopefor.Garey,Johnson,Karpandothermen(andwomen)TriedtomakeitorderNlogN.AmIamadfoolIfIspendmylifeingradschool,Foreverfollowingthelongestpath?Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelongestpath.Woh-oh-oh-oh,findthelongestpath!Woh-oh-oh-oh,findthelongestpath!IfyousaidPisNPtonight,Therewouldstillbepaperslefttowrite,Ihaveaweakness,I'maddictedtocompleteness,AndIkeepsearchingforthelongestpath.ThealgorithmIwouldliketoseeIsofpolynomialdegree,Butit'selusive:NobodyhasfoundconclusiveEvidencethatwecanfindalongestpath.Lyrics.Copyright©1988byDanielJ.Barrett.Music.SungtothetuneofTheLongesttimebyBillyJoel.RecordedbyDanBarrettwhileagradstudentatJohnsHopkinsduringadifficultalgorithmsfinal.57ThelongestpathIhavebeenhThetraveling-salesman

problem(TSP)Traveling-salesmanproblem:Asalesmanspendshistimevisitingncities(ornodes)cyclically.Inonetourhevisitseachcityjustonce,andfinishesupwherehestarted.Inwhatordershouldhevisitthemtominimisethedistancetravelled?Thereisanintegercostc(i,j)totravelfromcityitocityj,58Thetraveling-salesman

proTSP:NPCTheorem.Thetraveling-salesmanproblemisNP-complete.Pf.HAM-CYCLE≤PTSP.LetG=(V,E)beaninstanceofHAM-CYCLE.WeconstructaninstanceofTSPasfollows.WeformthecompletegraphG'=(V,E'),whereE'={(i,j):i,j∈Vandi≠j},andwedefinethecostfunctioncby59TSP:NPCTheorem.ThetravelingProof.graphGhasahamiltoniancycleifandonlyifgraphG'hasatourofcostatmost0.SupposethatgraphGhasahamiltoniancycleh.EachedgeinhbelongstoEandthushascost0inG'.Thus,hisatourinG'withcost0Conversely,supposethatgraphG'hasatourh'ofcostatmost0.SincethecostsoftheedgesinE'are0and1,thecostoftourh'isexactly0andeachedgeonthetourmusthavecost0.Therefore,h'containsonlyedgesinE.Weconcludethath'isahamiltoniancycleingraphG.60Proof.graphGhasahamiltoniNPProblems61NPProblems61Acompendiumof

NPoptimizationproblemsEditors:

PierluigiCrescenzi,andViggoKann

Subeditors:

MagnúsHalldórsson(retired)

GraphTheory:CoveringandPartitioning,SubgraphsandSupergraphs,SetsandPartitions.

MarekKarpinski

GraphTheory:VertexOrdering,NetworkDesign:CutsandConnectivity.

GerhardWoeginger

SequencingandScheduling.nada.kth.se/~viggo/problemlist/62Acompendiumof

NPoptimizatiTheNP-CompletenessColumnDavidJohnson.ACMTRANSACTIONSONALGORITHMS1:1,160-176(2019)63TheNP-CompletenessColumn63OpenProblemOpen:theVisibilityGraphRecognitionproblemisnotevenknowntobeinNP.

VisibilityGraphRecognitionproblem:GivenavisibilitygraphGandaHamiltoniancircuitC,determineinpolynomialtimewhetherthereisasimplepolygonwhosevertexvisibilitygraphisG,andwhoseboundarycorrespondstoC.VisibilityGraph:LetSbeasetofsimplepolygonalobstaclesintheplane,thenthenodesofthevisibilitygraphofarejusttheverticesofS,andthereisanedge(calledavisibilityedge)betweenverticesandiftheseverticesaremutuallyvisible.Asimplepolygonisapolygonwhichdoesnotintersectitselfanywhere.ThesearealsocalledJordanpolygons.64OpenProblemOpen:theVisibiliNPandComputational

Intractability叶德仕yedeshigmail65NPandComputational

Intractab

DecisionProblemsDecisionproblem.(theanswerissimply"yes"or"no")

Xisasetofstrings.Instance:strings.AlgorithmAsolvesproblemX:A(s)=yesiffs∈X.Optimizationproblems.inwhicheachfeasible(i.e.,"legal")solutionhasanassociatedvalue,andwewishtofindthefeasiblesolutionwiththebestvalue.66DecisionProblemsDecisioPolynomialtime.AlgorithmArunsinpoly-timeifforeverystrings,A(s)terminatesinatmostp(|s|)"steps",wherep(.)issomepolynomial.Certificationalgorithmintuition.Certifierviewsthingsfrom"managerial"viewpoint.Certifierdoesn'tdeterminewhethers∈Xonitsown;rather,itchecksaproposedcertificatetthats∈X.i.e.,certifierverifytheproposedsolutiontandtheinstanceswhetherC(s,t)isyes.67Polynomialtime.AlgorithmArDef.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,s∈XiffthereexistsastringtsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereexistsapoly-timecertifier.Remark.

NPstandsfornondeterministicpoly-time.68Def.AlgorithmC(s,t)isaceCertifiersandCertificates:

Composite(合数)COMPOSITES.Givenanintegers,isscomposite?Certificate.Anontrivialfactortofs.Notethatsuchacertificate

existsiffsiscomposite.Moreover|t|≤|s|.Certifier.booleanC(s,t){if(t≤1ort≥s)

returnfalseelseif(sisamultipleoft)

returntrueelse

returnfalse}69CertifiersandCertificateExampleInstance.

s=437,669.Certificate.

t=541or809.Conclusion.

COMPOSITESisinNP.70ExampleInstance.s=437,66

CertifiersandCertificates:

3-SatisfiabilitySAT.GivenaCNFformula,isthereasatisfyingassignment?Certificate.

Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Checkthateachclausein

hasatleastonetrueliteral.

Instance:Certificate:Conclusion.

SATisinNP.71CertifiersandCertificat

CertifiersandCertificates:

HamiltonianCycleHAM-CYCLE.GivenanundirectedgraphG=(V,E),doesthereexista

simplecycleCthatvisitseverynode?Certificate.Apermutationofthennodes.Certifier.CheckthatthepermutationcontainseachnodeinVexactly

once,andthatthereisanedgebetweeneachpairofadjacentnodesin

thepermutation.Conclusion.HAM-CYCLEisinNP.72CertifiersandCertifiP,NP,EXPP.Decisionproblemsforwhichthereisapoly-timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential-timealgorithm.NP.Decisionproblemsforwhichthereisapoly-timecertifier.73P,NP,EXPP.DecisionproblemsClaim.

Pf.ConsideranyproblemXinP.

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

Pf.ConsideranyproblemXinNP.Bydefinition,thereexistsapoly-timecertifierC(s,t)forX.

Tosolveinputs,runC(s,t)onallstringstwith|t|≤p(|s|).Returnyes,ifC(s,t)returnsyesforanyofthese.!74Claim.10TheMainQuestion:

PVersusNPDoesP=NP?[Cook1971,Edmonds,Levin,Yablonski,Gödel]Isthedecisionproblemaseasyasthecertificationproblem?Clay$1millionprize.EXPNPPEXPP=NPIfP=NPIfP≠NP75TheMainQuestion:

PVersusNAformual-language

FrameworkAnalphabet

Σisafinitesetofsymbols.Alanguage

LoverΣisanysetofstringsmadeupofsymbolsfromΣ.Forexample,Σ={0,1},

L={10,11,101,111,1011,1101,10001,...}Listhelanguageofbinaryrepresentationsofprimenumb