下载
加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 Computational.Complexity.A.Modern.Approach

Computational.Complexity.A.Modern.Approach.pdf

Computational.Complexity.A.Mode…

luoq
2011-01-14 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《Computational.Complexity.A.Modern.Approachpdf》,可适用于人文社科领域

ThispageintentionallyleftblankCOMPUTATIONALCOMPLEXITYThisbeginninggraduatetextbookdescribesbothrecentachievementsandclassicalresultsofcomputationalcomplexitytheoryRequiringessentiallynobackgroundapartfrommathematicalmaturity,thebookcanbeusedasareferenceforselfstudyforanyoneinterestedincomplexity,includingphysicists,mathematicians,andotherscientists,aswellasatextbookforavarietyofcoursesandseminarsMorethanexercisesareincludedwithaselectedhintsetThebookstartswithabroadintroductiontothefieldandprogressestoadvancedresultsContentsincludedefinitionofTuringmachinesandbasictimeandspacecomplexityclasses,probabilisticalgorithms,interactiveproofs,cryptography,quantumcomputation,lowerboundsforconcretecomputationalmodels(decisiontrees,communicationcomplexity,constantdepth,algebraicandmonotonecircuits,proofcomplexity),averagecasecomplexityandhardnessamplification,derandomizationandpseudorandomconstructions,andthePCPTheoremSanjeevAroraisaprofessorinthedepartmentofcomputerscienceatPrincetonUniversityHehasdonefoundationalworkonprobabilisticallycheckableproofsandapproximabilityofNPhardproblemsHeisthefoundingdirectoroftheCenterforComputationalIntractability,whichisfundedbytheNationalScienceFoundationBoazBarakisanassistantprofessorinthedepartmentofcomputerscienceatPrincetonUniversityHehasdonefoundationalworkincomputationalcomplexityandcryptography,especiallyindeveloping“nonblackbox”techniquesCOMPUTATIONALCOMPLEXITYAModernApproachSANJEEVARORAPrincetonUniversityBOAZBARAKPrincetonUniversityCAMBRIDGEUNIVERSITYPRESSCambridge,NewYork,Melbourne,Madrid,CapeTown,Singapore,SãoPauloCambridgeUniversityPressTheEdinburghBuilding,CambridgeCBRU,UKFirstpublishedinprintformatISBNISBN©SanjeevAroraandBoazBarakInformationonthistitle:wwwcambridgeorgThispublicationisincopyrightSubjecttostatutoryexceptionandtotheprovisionofrelevantcollectivelicensingagreements,noreproductionofanypartmaytakeplacewithoutthewrittenpermissionofCambridgeUniversityPressCambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyofurlsforexternalorthirdpartyinternetwebsitesreferredtointhispublication,anddoesnotguaranteethatanycontentonsuchwebsitesis,orwillremain,accurateorappropriatePublishedintheUnitedStatesofAmericabyCambridgeUniversityPress,NewYorkwwwcambridgeorgeBook(EBL)hardbackToourwivesSilviaandRavitContentsAboutthisbookpagexiiiAcknowledgmentsxviiIntroductionxixNotationalconventionsRepresentingobjectsasstringsDecisionproblemslanguagesBigohnotationexercisesPARTONE:BASICCOMPLEXITYCLASSESThecomputationalmodelandwhyitdoesn’tmatterModelingcomputation:WhatyoureallyneedtoknowTheTuringmachineEfficiencyandrunningtimeMachinesasstringsandtheuniversalTuringmachineUncomputability:AnintroductionTheClassPProofofTheorem:UniversalsimulationinO(TlogT)timechapternotesandhistoryexercisesNPandNPcompletenessTheClassNPReducibilityandNPcompletenessTheCookLevinTheorem:ComputationislocalThewebofreductionsDecisionversussearchcoNP,EXP,andNEXPMorethoughtsaboutP,NP,andallthatchapternotesandhistoryexercisesviiviiiContentsDiagonalizationTimeHierarchyTheoremNondeterministicTimeHierarchyTheoremLadner’sTheorem:ExistenceofNPintermediateproblemsOraclemachinesandthelimitsofdiagonalizationchapternotesandhistoryexercisesSpacecomplexityDefinitionofspaceboundedcomputationPSPACEcompletenessNLcompletenesschapternotesandhistoryexercisesThepolynomialhierarchyandalternationsTheClass�pThepolynomialhierarchyAlternatingTuringmachinesTimeversusalternations:TimespacetradeoffsforSATDefiningthehierarchyviaoraclemachineschapternotesandhistoryexercisesBooleancircuitsBooleancircuitsandPpolyUniformlygeneratedcircuitsTuringmachinesthattakeadvicePpolyandNPCircuitlowerboundsNonuniformHierarchyTheoremFinergradationsamongcircuitclassesCircuitsofexponentialsizechapternotesandhistoryexercisesRandomizedcomputationProbabilisticTuringmachinesSomeexamplesofPTMsOnesidedand“zerosided”error:RP,coRP,ZPPTherobustnessofourdefinitionsRelationshipbetweenBPPandotherclassesRandomizedreductionsRandomizedspaceboundedcomputationchapternotesandhistoryexercisesContentsixInteractiveproofsInteractiveproofs:SomevariationsPubliccoinsandAMIP=PSPACEThepoweroftheproverMultiproverinteractiveproofs(MIP)ProgramcheckingInteractiveproofforthepermanentchapternotesandhistoryexercisesCryptographyPerfectsecrecyanditslimitationsComputationalsecurity,onewayfunctions,andpseudorandomgeneratorsPseudorandomgeneratorsfromonewaypermutationsZeroknowledgeSomeapplicationschapternotesandhistoryexercisesQuantumcomputationQuantumweirdness:ThetwoslitexperimentQuantumsuperpositionandqubitsDefinitionofquantumcomputationandBQPGrover’ssearchalgorithmSimon’salgorithmShor’salgorithm:IntegerfactorizationusingquantumcomputersBQPandclassicalcomplexityclasseschapternotesandhistoryexercisesPCPtheoremandhardnessofapproximation:AnintroductionMotivation:ApproximatesolutionstoNPhardoptimizationproblemsTwoviewsofthePCPTheoremEquivalenceofthetwoviewsHardnessofapproximationforvertexcoverandindependentsetNP⊆PCP(poly(n),):PCPfromtheWalshHadamardcodechapternotesandhistoryexercisesPARTTWO:LOWERBOUNDSFORCONCRETECOMPUTATIONALMODELSDecisiontreesDecisiontreesanddecisiontreecomplexityCertificatecomplexityRandomizeddecisiontreesxContentsSometechniquesforprovingdecisiontreelowerboundschapternotesandhistoryexercisesCommunicationcomplexityDefinitionoftwopartycommunicationcomplexityLowerboundmethodsMultipartycommunicationcomplexityOverviewofothercommunicationmodelschapternotesandhistoryexercisesCircuitlowerbounds:Complexitytheory’sWaterlooACandHåstad’sSwitchingLemmaCircuitswith“counters”:ACCLowerboundsformonotonecircuitsCircuitcomplexity:ThefrontierApproachesusingcommunicationcomplexitychapternotesandhistoryexercisesProofcomplexitySomeexamplesPropositionalcalculusandresolutionOtherproofsystems:Atourd’horizonMetamathematicalmusingschapternotesandhistoryexercisesAlgebraiccomputationmodelsAlgebraicstraightlineprogramsandalgebraiccircuitsAlgebraiccomputationtreesTheBlumShubSmalemodelchapternotesandhistoryexercisesPARTTHREE:ADVANCEDTOPICSComplexityofcountingExamplesofcountingproblemsTheClass#P#PcompletenessToda’stheorem:PH⊆P#SATOpenproblemschapternotesandhistoryexercisesContentsxiAveragecasecomplexity:Levin’stheoryDistributionalproblemsanddistPFormalizationof“reallifedistributions”distnpanditscompleteproblemsPhilosophicalandpracticalimplicationschapternotesandhistoryexercisesHardnessamplificationanderrorcorrectingcodesMildtostronghardness:Yao’sXORlemmaTool:ErrorcorrectingcodesEfficientdecodingLocaldecodingandhardnessamplificationListdecodingLocallistdecoding:GettingtoBPP=PchapternotesandhistoryexercisesDerandomizationPseudorandomgeneratorsandderandomizationProofofTheorem:NisanWigdersonConstructionDerandomizationunderuniformassumptionsDerandomizationrequirescircuitlowerboundschapternotesandhistoryexercisesPseudorandomconstructions:ExpandersandextractorsRandomwalksandeigenvaluesExpandergraphsExplicitconstructionofexpandergraphsDeterministiclogspacealgorithmforundirectedconnectivityWeakrandomsourcesandextractorsPseudorandomgeneratorsforspaceboundedcomputationchapternotesandhistoryexercisesProofsofPCPtheoremsandtheFouriertransformtechniqueConstraintsatisfactionproblemswithnonbinaryalphabetProofofthePCPtheoremHardnessofCSPW:TradeoffbetweengapandalphabetsizeHåstad’sbitPCPTheoremandhardnessofMAXSATTool:TheFouriertransformtechniqueCoordinatefunctions,longCode,anditstestingProofofTheoremHardnessofapproximatingSETCOVEROtherPCPtheorems:AsurveyATransformingqCSPinstancesinto“nice”instanceschapternotesandhistoryexercisesxiiContentsWhyarecircuitlowerboundssodifficultDefinitionofnaturalproofsWhat’ssonaturalaboutnaturalproofsProofofTheoremAn“unnatural”lowerboundAphilosophicalviewchapternotesandhistoryexercisesAppendix:MathematicalbackgroundASets,functions,pairs,strings,graphs,logicAProbabilitytheoryANumbertheoryandgroupsAFinitefieldsABasicfactsfromlinearAlgebraAPolynomialsHintsandselectedexercisesMaintheoremsanddefinitionsBibliographyIndexComplexityclassindexAboutthisbookComputationalcomplexitytheoryhasdevelopedrapidlyinthepastthreedecadesThelistofsurprisingandfundamentalresultsprovedsincealonecouldfillabook:Theseincludenewprobabilisticdefinitionsofclassicalcomplexityclasses(IP=PSPACEandthePCPtheorems)andtheirimplicationsforthefieldofapproximationalgorithms,Shor’salgorithmtofactorintegersusingaquantumcomputer,anunderstandingofwhycurrentapproachestothefamousPversusNPwillnotbesuccessful,atheoryofderandomizationandpseudorandomnessbaseduponcomputationalhardness,andbeautifulconstructionsofpseudorandomobjectssuchasextractorsandexpandersThisbookaimstodescribesuchrecentachievementsofcomplexitytheoryinthecontextofmoreclassicalresultsItisintendedtoservebothasatextbookandasareferenceforselfstudyThismeansitmustsimultaneouslycatertomanyaudiences,anditiscarefullydesignedwiththatgoalinmindWeassumeessentiallynocomputationalbackgroundandveryminimalmathematicalbackground,whichwereviewinAppendixAWehavealsoprovidedaWebsiteforthisbookathttp:wwwcsprincetonedutheorycomplexitywithrelatedauxiliarymaterial,includingdetailedteachingplansforcoursesbasedonthisbook,adraftofallthebook’schapters,andlinkstootheronlineresourcescoveringrelatedtopicsThroughoutthebookweexplainthecontextinwhichacertainnotionisuseful,andwhythingsaredefinedinacertainwayWealsoillustratekeydefinitionswithexamplesTokeepthetextflowing,wehavetriedtominimizebibliographicreferences,exceptwhenresultshaveacquiredstandardnamesintheliterature,orwhenwefeltthatprovidingsomehistoryonaparticularresultservestoillustrateitsmotivationorcontext(Everychapterhasanotessectionthatcontainsafuller,thoughstillbrief,treatmentoftherelevantworks)Whenfacedwithachoice,wepreferredtousesimplerdefinitionsandproofsovershowingthemostgeneralormostoptimizedresultThebookisdividedintothreeparts:•PartI:BasiccomplexityclassesThispartprovidesabroadintroductiontothefieldStartingfromthedefinitionofTuringmachinesandthebasicnotionsofcomputabilitytheory,itcoversthebasictimeandspacecomplexityclassesandalsoincludesafewmoremoderntopicssuchasprobabilisticalgorithms,interactiveproofs,cryptography,quantumcomputers,andthePCPTheoremanditsapplicationsxiiixivAboutthisbook•PartII:LowerboundsonconcretecomputationalmodelsThispartdescribeslowerboundsonresourcesrequiredtosolvealgorithmictasksonconcretemodelssuchascircuitsanddecisiontreesSuchmodelsmayseematfirstsightverydifferentfromTuringmachines,butuponlookingdeeper,onefindsinterestinginterconnections•PartIII:AdvancedtopicsThispartislargelydevotedtodevelopmentssincethelatesItincludescountingcomplexity,averagecasecomplexity,hardnessamplification,derandomizationandpseudorandomness,theproofofthePCPtheorem,andnaturalproofsAlmosteverychapterinthebookcanbereadinisolation(thoughChapters,,andmustnotbeskipped)Thisisbydesignbecausethebookisaimedatmanyclassesofreaders:•Physicists,mathematicians,andotherscientistsThisgrouphasbecomeincreasinglyinterestedincomputationalcomplexitytheory,especiallybecauseofhighprofileresultssuchasShor’salgorithmandtherecentdeterministictestforprimalityThisintellectuallysophisticatedgroupwillbeabletoquicklyreadthroughPartIProgressingontoPartsIIandIII,theycanreadindividualchaptersandfindalmosteverythingtheyneedtounderstandcurrentresearch•ComputerscientistswhodonotworkincomplexitytheoryperseTheymayusethebookforselfstudy,reference,ortoteachanundergraduateorgraduatecourseintheoryofcomputationorcomplexitytheory•AnyoneprofessorsorstudentswhodoesresearchincomplexitytheoryorplanstodosoThecoverageofrecentresultsandadvancedtopicsisdetailedenoughtopreparereadersforresearchincomplexityandrelatedareasThisbookcanbeusedasatextbookforseveraltypesofcourses:•UndergraduatetheoryofcomputationManycomputerscience(CS)departmentsofferanundergraduateTheoryofComputationcourse,using,say,Sipser’sbookSipOurtextcouldbeusedtosupplementSipser’sbookwithcoverageofsomemoremoderntopics,suchasprobabilisticalgorithms,cryptography,andquantumcomputingUndergraduatestudentsmayfindthesemoreexcitingthantraditionaltopics,suchasautomatatheoryandthefinerdistinctionsofcomputabilitytheoryTheprerequisitemathematicalbackgroundwouldbesomecomfortwithmathematicalproofsanddiscretemathematics,ascoveredinthetypical“discretemath”or“mathforCS”coursescurrentlyofferedinmanyCSdepartments•IntroductiontocomputationalcomplexityforadvancedundergradsorbeginninggradsThebookcanbeusedasatextforanintroductorycomplexitycourseaimedatadvancedundergraduateorgraduatestudentsincomputerscience(replacingbookssuchasPapadimitriou’stextPapthatdonotcontainmanyrecentresults)SuchacoursewouldprobablyincludemanytopicsfromPartIandthenasprinklingfromPartsIIandIIIandassumesomebackgroundinalgorithmsandorthetheoryofcomputation•GraduatecomplexitycourseThebookcanserveasatextforagraduatecomplexitycoursethatpreparesgraduatestudentsforresearchincomplexitytheoryorrelatedareaslikealgorithmsandmachinelearningSuchacoursecanusePartItoreviewbasicmaterialandthenmoveontotheadvancedtopicsofPartsIIandIIIThebookcontainsfarmorematerialthancanbetaughtinoneterm,andweprovideonourWebsiteseveralalternativeoutlinesforsuchacourseAboutthisbookxv•GraduateseminarsoradvancedcoursesIndividualchaptersfromPartsIIandIIIcanbeusedinseminarsoradvancedcoursesonvarioustopicsincomplexitytheory(eg,derandomization,thePCPTheorem,lowerbounds)Weprovideseveralteachingplansandmaterialforsuchcoursesonthebook’sWebsiteIfyouusethebookinyourcourse,we’dlovetohearaboutitandgetyourfeedbackWeaskthatyoudonotpublishsolutionsforthebook’sexercisesontheWebthough,sootherpeoplecanusethemashomeworkandexamquestionsaswellAswefinishthisbook,wearesorelyawareofmanymoreexcitingresultsthatwehadtoleaveoutWehopethecopiousreferencestoothertextswillgivethereaderplentyofstartingpointsforfurtherexplorationsWealsoplantoperiodicallyupdatethebook’sWebsitewithpointerstonewerresultsorexpositionsthatmaybeofinteresttoourreadersAboveall,wehopethatthisbookconveysourexcitementaboutcomputationalcomplexityandtheinsightsitprovidesinahostofotherdisciplinesOnwardtoPversusNP!AcknowledgmentsOurunderstandingofcomplexitytheorywasshapedthroughinteractionswithourcolleagues,andwehavelearnedalotfromfartoomanypeopletomentionhereBoazwouldliketoespeciallythanktwomentorsOdedGoldreichandAviWigdersonwhointroducedtohimtheworldoftheoreticalcomputerscienceandstillinfluencemuchofhisthinkingonthisareaWethankLucaTrevisanforcoconceivingthebook(yearsago!)andhelpingtowritethefirstdraftsofacoupleofchaptersSeveralcolleagueshavegraciouslyagreedtoreviewforusearlydraftsofpartsofthisbookTheseincludeScottAaronson,NogaAlon,PaulBeame,IritDinur,VenkatesanGuruswami,JonathanKatz,ValentineKavanets,SubhashKhot,JirˇíMatoušek,KlausMeer,OrMeir,MoniNaor,AlexandrePinto,AlexanderRazborov,OdedRegev,OmerReingold,RonenShaltiel,MadhuSudan,AmnonTaShma,IannisTourlakis,ChrisUmans,SalilVadhan

用户评价(1)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/49

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利