Ajax Question
4/1/2011 6:01:00 AM
On Mar 31, 10:58 pm, musa...@att.net 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.?10TheMainQuestion:PVersusNP
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:P=NP?
Copyright©1990,MattGroening12Futurama:P=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.?10TheMainQuestion:PVersusNP
> 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:P=NP?
> Copyright©1990,MattGroening12Futurama:P=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?