AlgorithmAsolvesproblemX:A(s)=yesiffsX.Polynomialtime.

[musatov]

ExampleEx.ConstructionbelowcreatesacircuitKwhoseinputscanbesetsoKoutput­
strueiffgraphGhasanindependentsetofsize2.uvwn2G=(V,E),n=320EstablishingNP
+CompletenessRemark.Onceweestablishfirst"natural"NP
+completeproblem,othersfalllikedominoes.RecipetoestablishNP
+completenessofproblemY.â– Step1.ShowthatYisinNP.â– Step2.ChooseanNP
+completeproblemX.â– Step3.ProvethatXpY.Justification.IfXisanNP
+completeproblem,andYisaprobleminNPwiththepropertythatXPYthenYisNP
+complete.Pf.LetWbeanyprobleminNP.ThenWPXPY.â– Bytransitivity,WPY.â– HenceYisNP
+complete.â–ªbyassumptionbydefinitionofNP+complete
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ AlgorithmAsolvesproblemX:A(s)=yesiffsX.Polynomialtime.
AlgorithmArunsinpoly+timeifforeverystringsA(s)terminatesinatmostp(|
s|)"steps",wherep()=polynomial.PRIMES:X={2,3,5,7,11,13,17,23,29,31,37,41….}
Algorithm.
[Agrawal+Kayal+Saxena,2002]p(|s|)=|s|.lengthofs.
DefinitionofP=NP?decisionproblemswherethereisapolynominal
+timealgorithm.51,1651,17
GradeschooldivisionIsxamultipleofy?
MULTIPLE34,5134,39Euclid(300BCE)Arexandyrelativelyprime?
RELPRIME5153AKS(2002)Isxprime?
PRIMESacgggttttttanietherneitherDynamicprogrammingIstheeditdistancebetweenx­
andylessthan5?
EDIT+DISTANCEIsthereavectorxthatsatisfiesAx=b?DescriptionGauss
+EdmondseliminationAlgorithmLSOLVEProblemNoYes0112420315,4236100111011,111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
Page2
5NPCertificationalgorithmintuition.■Certifierviewsthingsfrom"managerial"vie­
wpoint.■Certifierdoesn'tdeterminewhethersXonitsown;rather,itchecksaproposed­
prooftthatsX.Def.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,sX­
iffthereexistsastringtsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereex­
istsapoly
+timecertifier.Remark.NPstandsfornondeterministicpolynomial
+time.C(s,t)isapoly+timealgorithmand|t|p(|
s|)forsomepolynomialp()."certificate"or"witness"6CertifiersandCertificates:­
CompositeCOMPOSITES.Givenanintegers,isscomposite?
Certificate.Anontrivialfactortofs.Notethatsuchacertificateexistsiffsiscompo­
site.Moreover|
t||
s|.Certifier.Instance.s=437,669.Certificate.t=541or809.Conclusion.COMPOSITE­
SisinNP.
437,669=541809booleanC(s,t)
{if(t1orts)returnfalseelseif(sisamultipleoft)returntrueelsereturnfalse}
7CertifiersandCertificates:
3+SatisfiabilitySAT.GivenaCNFformula,isthereasatisfyingassignment?
Certificate.Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Check­
thateachclauseinhasatleastonetrueliteral.Ex.Conclusion.SATisinNP.x1x2x3()x1­
x2x3()x1x2x4()x1x3x4()x1=1,x2=1,x3=0,x4=1instancescertificatet8Certifiersan­
dCertificates:HamiltonianCycleHAM
+CYCLE.GivenanundirectedgraphG=(V,E),doesthereexistasimplecycleCthatvisitse­
verynode?
Certificate.Apermutationofthennodes.Certifier.Checkthatthepermutationcontai­
nseachnodeinVexactlyonce,andthatthereisanedgebetweeneachpairofadjacentnodes­
inthepermutation.Conclusion.HAM
+CYCLEisinNP.instancescertificatet
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page3
9P,NP,EXPP.Decisionproblemsforwhichthereisapoly
+timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential
+timealgorithm.NP.Decisionproblemsforwhichthereisapoly
+timecertifier.Claim.PNP.Pf.ConsideranyproblemXinP.■Bydefinition,thereexist­
sapoly
+timealgorithmA(s)thatsolvesX.■Certificate:t=,certifierC(s,t)=A(s).▪Claim.N­
PEXP.Pf.ConsideranyproblemXinNP.â– Bydefinition,thereexistsapoly
+timecertifierC(s,t)forX.â– Tosolveinputs,runC(s,t)onallstringstwith|t|
p(|
s|).■Returnyes,ifC(s,t)returnsyesforanyofthese.▪10TheMainQuestionVersusNP­
DoesP=NP?
[Cook1971,Edmonds,Levin,Yablonski,Gödel]■Isthedecisionproblemaseasyasthecer­
tificationproblem?
â– Clay
$1millionprize.Ifyes:Efficientalgorithmsfor3+COLOR,TSP,FACTOR,SAT,
…Ifno:Noefficientalgorithmspossiblefor3+COLOR,TSP,SAT,…
ConsensusopiniononP=NP?
Probablyno.EXPNPPIfPNPIfP=NPEXPP=NPwouldbreakRSAcryptography(andpotentially­
collapseeconomy)11TheSimpson's=NP?
Copyright©1990,MattGroening12Futurama=NP?
Copyright©2000,TwentiethCenturyFox
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page4
13LookingforaJob?
SomewritersfortheSimpsonsandFuturama.■J.StewardBurns.M.S.inmathematics,Berk­
eley,
1993.â– DavidX.Cohen.M.S.incomputerscience,Berkeley,
1992.â– AlJean.B.S.inmathematics,Harvard,
1981.â– KenKeeler.Ph.D.inappliedmathematics,Harvard,
1990.â– JeffWestbrook.Ph.D.incomputerscience,Princeton,1989.8.4NP
+Completeness15PolynomialTransformationDef.ProblemXpolynomialreduces(Cook)t­
oproblemYifarbitraryinstancesofproblemXcanbesolvedusing:■Polynomialnumberof­
standardcomputationalsteps,plus■Polynomialnumberofcallstooraclethatsolvespr­
oblemY.Def.ProblemXpolynomialtransforms(Karp)toproblemYifgivenanyinputxtoX,­
wecanconstructaninputysuchthatxisayesinstanceofXiffyisayesinstanceofY.Note.­
PolynomialtransformationispolynomialreductionwithjustonecalltooracleforY,ex­
actlyattheendofthealgorithmforX.Almostallpreviousreductionswereofthisform.O­
penquestion.Arethesetwoconceptsthesame?
werequire|y|tobeofsizepolynomialin|x|
weabusenotationpandblurdistinction16NP+CompleteNP
+complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,XpY.Theorem.­
SupposeYisanNP
+completeproblem.ThenYissolvableinpoly
+timeiffP=NP.Pf.IfP=NPthenYcanbesolvedinpoly
+timesinceYisinNP.Pf.SupposeYcanbesolvedinpoly
+time.â– LetXbeanyprobleminNP.SinceXpY,wecansolveXinpoly
+time.ThisimpliesNPP.■WealreadyknowPNP.ThusP=NP.▪Fundamentalquestion.Dother­
eexist"natural"NP
+completeproblems?
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page5
17¬10???outputinputshard+codedinputsyes:
101CircuitSatisfiabilityCIRCUIT
+SAT.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawaytose­
tthecircuitinputssothattheoutputis1?
18sketchypartofproof;fixingthenumberofbitsisimportant,andreflectsbasicdisti­
nctionbetweenalgorithmsandcircuitsThe"First"NP
+CompleteProblemTheorem.CIRCUIT+SATisNP+complete.
[Cook1971,Levin1973]Pf.
(sketch)â– Anyalgorithmthattakesafixednumberofbitsnasinputandproducesayes/
noanswercanberepresentedbysuchacircuit.Moreover,ifalgorithmtakespoly
+time,thencircuitisofpoly+size.â– ConsidersomeproblemXinNP.Ithasapoly
+timecertifierC(s,t).TodeterminewhethersisinX,needtoknowifthereexistsacerti­
ficatetoflengthp(|
s|)suchthatC(s,t)=yes.â– ViewC(s,t)asanalgorithmon|s|+p(|
s|)bits(inputs,certificatet)andconvertitintoapoly+sizecircuitK.–
first|
s|bitsarehard+codedwiths–remainingp(|
s|)bitsrepresentbitsoft■CircuitKissatisfiableiffC(s,t)=yes.19¬u
+v1independentsetofsize2?ninputs(nodesinindependentset)hard
+codedinputs(graphdescription)u+w0v+w1u?v?w?setofsize2?
bothendpointsofsomeedgehavebeenchosen?independentset?

 

[musatov]

On Mar 31, 10:58 pm, (e-mail address removed) wrote:
..ConstructionbelowcreatesacircuitKwhoseinputscanbesetsoKoutput­
strueiffgraphGhasanindependentsetofsize2.uvwn2G=(V,E),n=320EstablishingNP
+CompletenessRemark.Onceweestablishfirst"natural"NP
+completeproblem,othersfalllikedominoes.RecipetoestablishNP
+completenessofproblemY.â– Step1.ShowthatYisinNP.â– Step2.ChooseanNP
+completeproblemX.â– Step3.ProvethatXpY.Justification.IfXisanNP
+completeproblem,andYisaprobleminNPwiththepropertythatXPYthenYisNP
+complete.Pf.LetWbeanyprobleminNP.ThenWPXPY.â– Bytransitivity,WPY.â– HenceYisNP
+complete.â–ªbyassumptionbydefinitionofNP+complete
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+ AlgorithmAsolvesproblemX:A(s)=yesiffsX.Polynomialtime.
AlgorithmArunsinpoly+timeifforeverystringsA(s)terminatesinatmostp(|
s|)"steps",wherep()=polynomial.PRIMES:X={2,3,5,7,11,13,17,23,29,31,37,41….}
Algorithm.
[Agrawal+Kayal+Saxena,2002]p(|s|)=|s|.lengthofs.
DefinitionofP=NP?decisionproblemswherethereisapolynominal
+timealgorithm.51,1651,17
GradeschooldivisionIsxamultipleofy?
MULTIPLE34,5134,39Euclid(300BCE)Arexandyrelativelyprime?
RELPRIME5153AKS(2002)Isxprime?
PRIMESacgggttttttanietherneitherDynamicprogrammingIstheeditdistancebetweenx­­
andylessthan5?
EDIT+DISTANCEIsthereavectorxthatsatisfiesAx=b?DescriptionGauss
+EdmondseliminationAlgorithmLSOLVEProblemNoYes0112420315,4236100111011,111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
Page2
5NPCertificationalgorithmintuition.■Certifierviewsthingsfrom"managerial"vie­­
wpoint.■Certifierdoesn'tdeterminewhethersXonitsown;rather,itchecksaproposed­­
prooftthatsX.Def.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,sX­­
iffthereexistsastringtsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereex­­
istsapoly
+timecertifier.Remark.NPstandsfornondeterministicpolynomial
+time.C(s,t)isapoly+timealgorithmand|t|p(|
s|)forsomepolynomialp()."certificate"or"witness"6CertifiersandCertificates:­­
CompositeCOMPOSITES.Givenanintegers,isscomposite?
Certificate.Anontrivialfactortofs.Notethatsuchacertificateexistsiffsiscompo­­
site.Moreover|
t||
s|.Certifier.Instance.s=437,669.Certificate.t=541or809.Conclusion.COMPOSITE­­
SisinNP.
437,669=541809booleanC(s,t)
{if(t1orts)returnfalseelseif(sisamultipleoft)returntrueelsereturnfalse}
7CertifiersandCertificates:
3+SatisfiabilitySAT.GivenaCNFformula,isthereasatisfyingassignment?
Certificate.Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Check­­
thateachclauseinhasatleastonetrueliteral.Ex.Conclusion.SATisinNP.x1x2x3()x1­­
x2x3()x1x2x4()x1x3x4()x1=1,x2=1,x3=0,x4=1instancescertificatet8Certifiersan­­
dCertificates:HamiltonianCycleHAM
+CYCLE.GivenanundirectedgraphG=(V,E),doesthereexistasimplecycleCthatvisitse­­
verynode?
Certificate.Apermutationofthennodes.Certifier.Checkthatthepermutationcontai­­
nseachnodeinVexactlyonce,andthatthereisanedgebetweeneachpairofadjacentnodes­­
inthepermutation.Conclusion.HAM
+CYCLEisinNP.instancescertificatet
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+
+++++++++
Page3
9P,NP,EXPP.Decisionproblemsforwhichthereisapoly
+timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential
+timealgorithm.NP.Decisionproblemsforwhichthereisapoly
+timecertifier.Claim.PNP.Pf.ConsideranyproblemXinP.■Bydefinition,thereexist­­
sapoly
+timealgorithmA(s)thatsolvesX.■Certificate:t=,certifierC(s,t)=A(s).▪Claim.N­­
PEXP.Pf.ConsideranyproblemXinNP.â– Bydefinition,thereexistsapoly
+timecertifierC(s,t)forX.â– Tosolveinputs,runC(s,t)onallstringstwith|t|
p(|
s|).■Returnyes,ifC(s,t)returnsyesforanyofthese.▪10TheMainQuestionVersusNP­­
DoesP=NP?
[Cook1971,Edmonds,Levin,Yablonski,Gödel]■Isthedecisionproblemaseasyasthecer­­
tificationproblem?
â– Clay
$1millionprize.Ifyes:Efficientalgorithmsfor3+COLOR,TSP,FACTOR,SAT,
…Ifno:Noefficientalgorithmspossiblefor3+COLOR,TSP,SAT,…
ConsensusopiniononP=NP?
Probablyno.EXPNPPIfPNPIfP=NPEXPP=NPwouldbreakRSAcryptography(andpotentially­­
collapseeconomy)11TheSimpson's=NP?
Copyright©1990,MattGroening12Futurama=NP?
Copyright©2000,TwentiethCenturyFox
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+
+++++++++
Page4
13LookingforaJob?
SomewritersfortheSimpsonsandFuturama.■J.StewardBurns.M.S.inmathematics,Berk­­
eley,
1993.â– DavidX.Cohen.M.S.incomputerscience,Berkeley,
1992.â– AlJean.B.S.inmathematics,Harvard,
1981.â– KenKeeler.Ph.D.inappliedmathematics,Harvard,
1990.â– JeffWestbrook.Ph.D.incomputerscience,Princeton,1989.8.4NP
+Completeness15PolynomialTransformationDef.ProblemXpolynomialreduces(Cook)t­­
oproblemYifarbitraryinstancesofproblemXcanbesolvedusing:■Polynomialnumberof­­
standardcomputationalsteps,plus■Polynomialnumberofcallstooraclethatsolvespr­­
oblemY.Def.ProblemXpolynomialtransforms(Karp)toproblemYifgivenanyinputxtoX,­­
wecanconstructaninputysuchthatxisayesinstanceofXiffyisayesinstanceofY.Note.­­
PolynomialtransformationispolynomialreductionwithjustonecalltooracleforY,ex­­
actlyattheendofthealgorithmforX.Almostallpreviousreductionswereofthisform.O­­
penquestion.Arethesetwoconceptsthesame?
werequire|y|tobeofsizepolynomialin|x|
weabusenotationpandblurdistinction16NP+CompleteNP
+complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,XpY.Theorem.­­
SupposeYisanNP
+completeproblem.ThenYissolvableinpoly
+timeiffP=NP.Pf.IfP=NPthenYcanbesolvedinpoly
+timesinceYisinNP.Pf.SupposeYcanbesolvedinpoly
+time.â– LetXbeanyprobleminNP.SinceXpY,wecansolveXinpoly
+time.ThisimpliesNPP.■WealreadyknowPNP.ThusP=NP.▪Fundamentalquestion.Dother­­
eexist"natural"NP
+completeproblems?
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+
+++++++++
Page5
17¬10???outputinputshard+codedinputsyes:
101CircuitSatisfiabilityCIRCUIT
+SAT.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawaytose­­
tthecircuitinputssothattheoutputis1?
18sketchypartofproof;fixingthenumberofbitsisimportant,andreflectsbasicdisti­­
nctionbetweenalgorithmsandcircuitsThe"First"NP
+CompleteProblemTheorem.CIRCUIT+SATisNP+complete.
[Cook1971,Levin1973]Pf.
(sketch)â– Anyalgorithmthattakesafixednumberofbitsnasinputandproducesayes/
noanswercanberepresentedbysuchacircuit.Moreover,ifalgorithmtakespoly
+time,thencircuitisofpoly+size.â– ConsidersomeproblemXinNP.Ithasapoly
+timecertifierC(s,t).TodeterminewhethersisinX,needtoknowifthereexistsacerti­­
ficatetoflengthp(|
s|)suchthatC(s,t)=yes.â– ViewC(s,t)asanalgorithmon|s|+p(|
s|)bits(inputs,certificatet)andconvertitintoapoly+sizecircuitK.–
first|
s|bitsarehard+codedwiths–remainingp(|
s|)bitsrepresentbitsoft■CircuitKissatisfiableiffC(s,t)=yes.19¬u
+v1independentsetofsize2?ninputs(nodesinindependentset)hard
+codedinputs(graphdescription)u+w0v+w1u?v?w?setofsize2?
bothendpointsofsomeedgehavebeenchosen?independentset?

ExampleEx.ConstructionbelowcreatesacircuitKwhoseinputscanbesetsoKoutput­
strueiffgraphGhasanindependentsetofsize2.uvwn2G=(V,E),n=320EstablishingNP
+CompletenessRemark.Onceweestablishfirst"natural"NP
+completeproblem,othersfalllikedominoes.RecipetoestablishNP
+completenessofproblemY.â– Step1.ShowthatYisinNP.â– Step2.ChooseanNP
+completeproblemX.â– Step3.ProvethatXpY.Justification.IfXisanNP
+completeproblem,andYisaprobleminNPwiththepropertythatXPYthenYisNP
+complete.Pf.LetWbeanyprobleminNP.ThenWPXPY.â– Bytransitivity,WPY.â– HenceYisNP
+complete.â–ªbyassumptionbydefinitionofNP+complete
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ AlgorithmAsolvesproblemX:A(s)=yesiffsX.Polynomialtime.
AlgorithmArunsinpoly+timeifforeverystringsA(s)terminatesinatmostp(|
s|)"steps",wherep()=polynomial.PRIMES:X={2,3,5,7,11,13,17,23,29,31,37,41….}
Algorithm.
[Agrawal+Kayal+Saxena,2002]p(|s|)=|s|.lengthofs.
DefinitionofP=NP?decisionproblemswherethereisapolynominal
+timealgorithm.51,1651,17
GradeschooldivisionIsxamultipleofy?
MULTIPLE34,5134,39Euclid(300BCE)Arexandyrelativelyprime?
RELPRIME5153AKS(2002)Isxprime?
PRIMESacgggttttttanietherneitherDynamicprogrammingIstheeditdistancebetweenx­­
andylessthan5?
EDIT+DISTANCEIsthereavectorxthatsatisfiesAx=b?DescriptionGauss
+EdmondseliminationAlgorithmLSOLVEProblemNoYes0112420315,4236100111011,111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
Page2
5NPCertificationalgorithmintuition.■Certifierviewsthingsfrom"managerial"vie­­
wpoint.■Certifierdoesn'tdeterminewhethersXonitsown;rather,itchecksaproposed­­
prooftthatsX.Def.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,sX­­
iffthereexistsastringtsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereex­­
istsapoly
+timecertifier.Remark.NPstandsfornondeterministicpolynomial
+time.C(s,t)isapoly+timealgorithmand|t|p(|
s|)forsomepolynomialp()."certificate"or"witness"6CertifiersandCertificates:­­
CompositeCOMPOSITES.Givenanintegers,isscomposite?
Certificate.Anontrivialfactortofs.Notethatsuchacertificateexistsiffsiscompo­­
site.Moreover|
t||
s|.Certifier.Instance.s=437,669.Certificate.t=541or809.Conclusion.COMPOSITE­­
SisinNP.
437,669=541809booleanC(s,t)
{if(t1orts)returnfalseelseif(sisamultipleoft)returntrueelsereturnfalse}
7CertifiersandCertificates:
3+SatisfiabilitySAT.GivenaCNFformula,isthereasatisfyingassignment?
Certificate.Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Check­­
thateachclauseinhasatleastonetrueliteral.Ex.Conclusion.SATisinNP.x1x2x3()x1­­
x2x3()x1x2x4()x1x3x4()x1=1,x2=1,x3=0,x4=1instancescertificatet8Certifiersan­­
dCertificates:HamiltonianCycleHAM
+CYCLE.GivenanundirectedgraphG=(V,E),doesthereexistasimplecycleCthatvisitse­­
verynode?
Certificate.Apermutationofthennodes.Certifier.Checkthatthepermutationcontai­­
nseachnodeinVexactlyonce,andthatthereisanedgebetweeneachpairofadjacentnodes­­
inthepermutation.Conclusion.HAM
+CYCLEisinNP.instancescertificatet
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page3
9P,NP,EXPP.Decisionproblemsforwhichthereisapoly
+timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential
+timealgorithm.NP.Decisionproblemsforwhichthereisapoly
+timecertifier.Claim.PNP.Pf.ConsideranyproblemXinP.■Bydefinition,thereexist­­
sapoly
+timealgorithmA(s)thatsolvesX.■Certificate:t=,certifierC(s,t)=A(s).▪Claim.N­­
PEXP.Pf.ConsideranyproblemXinNP.â– Bydefinition,thereexistsapoly
+timecertifierC(s,t)forX.â– Tosolveinputs,runC(s,t)onallstringstwith|t|
p(|
s|).■Returnyes,ifC(s,t)returnsyesforanyofthese.▪10TheMainQuestionVersusNP­­
DoesP=NP?
[Cook1971,Edmonds,Levin,Yablonski,Gödel]■Isthedecisionproblemaseasyasthecer­­
tificationproblem?
â– Clay
$1millionprize.Ifyes:Efficientalgorithmsfor3+COLOR,TSP,FACTOR,SAT,
…Ifno:Noefficientalgorithmspossiblefor3+COLOR,TSP,SAT,…
ConsensusopiniononP=NP?
Probablyno.EXPNPPIfPNPIfP=NPEXPP=NPwouldbreakRSAcryptography(andpotentially­­
collapseeconomy)11TheSimpson's=NP?
Copyright©1990,MattGroening12Futurama=NP?
Copyright©2000,TwentiethCenturyFox
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page4
13LookingforaJob?
SomewritersfortheSimpsonsandFuturama.■J.StewardBurns.M.S.inmathematics,Berk­­
eley,
1993.â– DavidX.Cohen.M.S.incomputerscience,Berkeley,
1992.â– AlJean.B.S.inmathematics,Harvard,
1981.â– KenKeeler.Ph.D.inappliedmathematics,Harvard,
1990.â– JeffWestbrook.Ph.D.incomputerscience,Princeton,1989.8.4NP
+Completeness15PolynomialTransformationDef.ProblemXpolynomialreduces(Cook)t­­
oproblemYifarbitraryinstancesofproblemXcanbesolvedusing:■Polynomialnumberof­­
standardcomputationalsteps,plus■Polynomialnumberofcallstooraclethatsolvespr­­
oblemY.Def.ProblemXpolynomialtransforms(Karp)toproblemYifgivenanyinputxtoX,­­
wecanconstructaninputysuchthatxisayesinstanceofXiffyisayesinstanceofY.Note.­­
PolynomialtransformationispolynomialreductionwithjustonecalltooracleforY,ex­­
actlyattheendofthealgorithmforX.Almostallpreviousreductionswereofthisform..O­­
penquestion.Arethesetwoconceptsthesame?
werequire|y|tobeofsizepolynomialin|x|
weabusenotationpandblurdistinction16NP+CompleteNP
+complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,XpY.Theorem.­­
SupposeYisanNP
+completeproblem.ThenYissolvableinpoly
+timeiffP=NP.Pf.IfP=NPthenYcanbesolvedinpoly
+timesinceYisinNP.Pf.SupposeYcanbesolvedinpoly
+time.â– LetXbeanyprobleminNP.SinceXpY,wecansolveXinpoly
+time.ThisimpliesNPP.■WealreadyknowPNP.ThusP=NP.▪Fundamentalquestion.Dother­­
eexist"natural"NP
+completeproblems?
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page5
17¬10???outputinputshard+codedinputsyes:
101CircuitSatisfiabilityCIRCUIT
+SAT.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawaytose­­
tthecircuitinputssothattheoutputis1?
18sketchypartofproof;fixingthenumberofbitsisimportant,andreflectsbasicdisti­­
nctionbetweenalgorithmsandcircuitsThe"First"NP
+CompleteProblemTheorem.CIRCUIT+SATisNP+complete.
[Cook1971,Levin1973]Pf.
(sketch)â– Anyalgorithmthattakesafixednumberofbitsnasinputandproducesayes/
noanswercanberepresentedbysuchacircuit.Moreover,ifalgorithmtakespoly
+time,thencircuitisofpoly+size.â– ConsidersomeproblemXinNP.Ithasapoly
+timecertifierC(s,t).TodeterminewhethersisinX,needtoknowifthereexistsacerti­­
ficatetoflengthp(|
s|)suchthatC(s,t)=yes.â– ViewC(s,t)asanalgorithmon|s|+p(|
s|)bits(inputs,certificatet)andconvertitintoapoly+sizecircuitK.–
first|
s|bitsarehard+codedwiths–remainingp(|
s|)bitsrepresentbitsoft■CircuitKissatisfiableiffC(s,t)=yes.19¬u
+v1independentsetofsize2?ninputs(nodesinindependentset)hard
+codedinputs(graphdescription)u+w0v+w1u?v?w?setofsize2?
bothendpointsofsomeedgehavebeenchosen?independentset?

P = NP?

 

[musatov]

ExampleEx.ConstructionbelowcreatesacircuitKwhoseinputscanbesetsoKoutput­
strueiffgraphGhasanindependentsetofsize2.uvwn2G=(V,E),n=320EstablishingNP
+CompletenessRemark.Onceweestablishfirst"natural"NP
+completeproblem,othersfalllikedominoes.RecipetoestablishNP
+completenessofproblemY.â– Step1.ShowthatYisinNP.â– Step2.ChooseanNP
+completeproblemX.â– Step3.ProvethatXpY.Justification.IfXisanNP
+completeproblem,andYisaprobleminNPwiththepropertythatXPYthenYisNP
+complete.Pf.LetWbeanyprobleminNP.ThenWPXPY.â– Bytransitivity,WPY.â– HenceYisNP
+complete.â–ªbyassumptionbydefinitionofNP+complete
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ AlgorithmAsolvesproblemX:A(s)=yesiffsX.Polynomialtime.
AlgorithmArunsinpoly+timeifforeverystringsA(s)terminatesinatmostp(|
s|)"steps",wherep()=polynomial.PRIMES:X={2,3,5,7,11,13,17,23,29,31,37,41….}
Algorithm.
[Agrawal+Kayal+Saxena,2002]p(|s|)=|s|.lengthofs.
DefinitionofP=NP?decisionproblemswherethereisapolynominal
+timealgorithm.51,1651,17
GradeschooldivisionIsxamultipleofy?
MULTIPLE34,5134,39Euclid(300BCE)Arexandyrelativelyprime?
RELPRIME5153AKS(2002)Isxprime?
PRIMESacgggttttttanietherneitherDynamicprogrammingIstheeditdistancebetweenx­­
andylessthan5?
EDIT+DISTANCEIsthereavectorxthatsatisfiesAx=b?DescriptionGauss
+EdmondseliminationAlgorithmLSOLVEProblemNoYes0112420315,4236100111011,111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
Page2
5NPCertificationalgorithmintuition.■Certifierviewsthingsfrom"managerial"vie­­
wpoint.■Certifierdoesn'tdeterminewhethersXonitsown;rather,itchecksaproposed­­
prooftthatsX.Def.AlgorithmC(s,t)isacertifierforproblemXifforeverystrings,sX­­
iffthereexistsastringtsuchthatC(s,t)=yes.NP.Decisionproblemsforwhichthereex­­
istsapoly
+timecertifier.Remark.NPstandsfornondeterministicpolynomial
+time.C(s,t)isapoly+timealgorithmand|t|p(|
s|)forsomepolynomialp()."certificate"or"witness"6CertifiersandCertificates:­­
CompositeCOMPOSITES.Givenanintegers,isscomposite?
Certificate.Anontrivialfactortofs.Notethatsuchacertificateexistsiffsiscompo­­
site.Moreover|
t||
s|.Certifier.Instance.s=437,669.Certificate.t=541or809.Conclusion.COMPOSITE­­
SisinNP.
437,669=541809booleanC(s,t)
{if(t1orts)returnfalseelseif(sisamultipleoft)returntrueelsereturnfalse}
7CertifiersandCertificates:
3+SatisfiabilitySAT.GivenaCNFformula,isthereasatisfyingassignment?
Certificate.Anassignmentoftruthvaluestothenbooleanvariables.Certifier.Check­­
thateachclauseinhasatleastonetrueliteral.Ex.Conclusion.SATisinNP.x1x2x3()x1­­
x2x3()x1x2x4()x1x3x4()x1=1,x2=1,x3=0,x4=1instancescertificatet8Certifiersan­­
dCertificates:HamiltonianCycleHAM
+CYCLE.GivenanundirectedgraphG=(V,E),doesthereexistasimplecycleCthatvisitse­­
verynode?
Certificate.Apermutationofthennodes.Certifier.Checkthatthepermutationcontai­­
nseachnodeinVexactlyonce,andthatthereisanedgebetweeneachpairofadjacentnodes­­
inthepermutation.Conclusion.HAM
+CYCLEisinNP.instancescertificatet
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page3
9P,NP,EXPP.Decisionproblemsforwhichthereisapoly
+timealgorithm.EXP.Decisionproblemsforwhichthereisanexponential
+timealgorithm.NP.Decisionproblemsforwhichthereisapoly
+timecertifier.Claim.PNP.Pf.ConsideranyproblemXinP.■Bydefinition,thereexist­­
sapoly
+timealgorithmA(s)thatsolvesX.■Certificate:t=,certifierC(s,t)=A(s).▪Claim.N­­
PEXP.Pf.ConsideranyproblemXinNP.â– Bydefinition,thereexistsapoly
+timecertifierC(s,t)forX.â– Tosolveinputs,runC(s,t)onallstringstwith|t|
p(|
s|).■Returnyes,ifC(s,t)returnsyesforanyofthese.▪10TheMainQuestionVersusNP­­
DoesP=NP?
[Cook1971,Edmonds,Levin,Yablonski,Gödel]■Isthedecisionproblemaseasyasthecer­­
tificationproblem?
â– Clay
$1millionprize.Ifyes:Efficientalgorithmsfor3+COLOR,TSP,FACTOR,SAT,
…Ifno:Noefficientalgorithmspossiblefor3+COLOR,TSP,SAT,…
ConsensusopiniononP=NP?
Probablyno.EXPNPPIfPNPIfP=NPEXPP=NPwouldbreakRSAcryptography(andpotentially­­
collapseeconomy)11TheSimpson's=NP?
Copyright©1990,MattGroening12Futurama=NP?
Copyright©2000,TwentiethCenturyFox
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page4
13LookingforaJob?
SomewritersfortheSimpsonsandFuturama.■J.StewardBurns.M.S.inmathematics,Berk­­
eley,
1993.â– DavidX.Cohen.M.S.incomputerscience,Berkeley,
1992.â– AlJean.B.S.inmathematics,Harvard,
1981.â– KenKeeler.Ph.D.inappliedmathematics,Harvard,
1990.â– JeffWestbrook.Ph.D.incomputerscience,Princeton,1989.8.4NP
+Completeness15PolynomialTransformationDef.ProblemXpolynomialreduces(Cook)t­­
oproblemYifarbitraryinstancesofproblemXcanbesolvedusing:■Polynomialnumberof­­
standardcomputationalsteps,plus■Polynomialnumberofcallstooraclethatsolvespr­­
oblemY.Def.ProblemXpolynomialtransforms(Karp)toproblemYifgivenanyinputxtoX,­­
wecanconstructaninputysuchthatxisayesinstanceofXiffyisayesinstanceofY.Note.­­
PolynomialtransformationispolynomialreductionwithjustonecalltooracleforY,ex­­
actlyattheendofthealgorithmforX.Almostallpreviousreductionswereofthisform..O­­
penquestion.Arethesetwoconceptsthesame?
werequire|y|tobeofsizepolynomialin|x|
weabusenotationpandblurdistinction16NP+CompleteNP
+complete.AproblemYinNPwiththepropertythatforeveryproblemXinNP,XpY.Theorem.­­
SupposeYisanNP
+completeproblem.ThenYissolvableinpoly
+timeiffP=NP.Pf.IfP=NPthenYcanbesolvedinpoly
+timesinceYisinNP.Pf.SupposeYcanbesolvedinpoly
+time.â– LetXbeanyprobleminNP.SinceXpY,wecansolveXinpoly
+time.ThisimpliesNPP.■WealreadyknowPNP.ThusP=NP.▪Fundamentalquestion.Dother­­
eexist"natural"NP
+completeproblems?
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+
+++++++++
Page5
17¬10???outputinputshard+codedinputsyes:
101CircuitSatisfiabilityCIRCUIT
+SAT.GivenacombinationalcircuitbuiltoutofAND,OR,andNOTgates,isthereawaytose­­
tthecircuitinputssothattheoutputis1?
18sketchypartofproof;fixingthenumberofbitsisimportant,andreflectsbasicdisti­­
nctionbetweenalgorithmsandcircuitsThe"First"NP
+CompleteProblemTheorem.CIRCUIT+SATisNP+complete.
[Cook1971,Levin1973]Pf.
(sketch)â– Anyalgorithmthattakesafixednumberofbitsnasinputandproducesayes/
noanswercanberepresentedbysuchacircuit.Moreover,ifalgorithmtakespoly
+time,thencircuitisofpoly+size.â– ConsidersomeproblemXinNP.Ithasapoly
+timecertifierC(s,t).TodeterminewhethersisinX,needtoknowifthereexistsacerti­­
ficatetoflengthp(|
s|)suchthatC(s,t)=yes.â– ViewC(s,t)asanalgorithmon|s|+p(|
s|)bits(inputs,certificatet)andconvertitintoapoly+sizecircuitK.–
first|
s|bitsarehard+codedwiths–remainingp(|
s|)bitsrepresentbitsoft■CircuitKissatisfiableiffC(s,t)=yes.19¬u
+v1independentsetofsize2?ninputs(nodesinindependentset)hard
+codedinputs(graphdescription)u+w0v+w1u?v?w?setofsize2?
bothendpointsofsomeedgehavebeenchosen?independentset?

P = NP?
10 standard
'Yes'.

 

[huhie]

****