加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 Complexity Theory A Modern Approach draft

Complexity Theory A Modern Approach draft.pdf

Complexity Theory A Modern Appr…

zuozuokun
2010-10-13 0人阅读 举报 0 0 暂无简介

简介:本文档为《Complexity Theory A Modern Approach draftpdf》,可适用于高等教育领域

DRAFTiComputationalComplexity:AModernApproachDraftofabook:DatedAugustCommentswelcome!SanjeevAroraandBoazBarakPrincetonUniversity{arora,boaz}csprincetoneduNottobereproducedordistributedwithouttheauthor’spermissionSomechaptersaremorefinishedthanothersReferencesandattributionsareverypreliminaryandweapologizeinadvanceforanyomissions(buthopeyouwillneverthelesspointthemouttous)DRAFTiiDRAFTAboutthisbookComputationalcomplexitytheoryhasdevelopedrapidlyinthepastthreedecadesThelistofsurprisingandfundamentalresultsprovedsincealonecouldfillabook:theseincludenewprobabilisticdefinitionsofclassicalcomplexityclasses(IP=PSPACEandthePCPTheorems)andtheirimplicationsforthefieldofapproximationalgorithmsShor’salgorithmtofactorintegersusingaquantumcomputeranunderstandingofwhycurrentapproachestothefamousPversusNPwillnotbesuccessfulatheoryofderandomizationandpseudorandomnessbaseduponcomputationalhardnessandbeautifulconstructionsofpseudorandomobjectssuchasextractorsandexpandersThisbookaimstodescribesuchrecentachievementsofcomplexitytheoryinthecontextoftheclassicalresultsItisintendedtobeatextandaswellasareferenceforselfstudyThismeansitmustsimultaneouslycatertomanyaudiences,anditiscarefullydesignedwiththatgoalThroughoutthebookweexplainthecontextinwhichacertainnotionisuseful,andwhythingsaredefinedinacertainwayExamplesandsolvedexercisesaccompanykeydefinitionsThebookhasthreepartsandanappendixPartI:Basiccomplexityclasses:ThispartprovidesabroadintroductiontothefieldandcoversbasicallythesamegroundasPapadimitriou’stextfromtheearlysbutmorequicklyItmaybesuitableforanundergraduatecoursethatisanalternativetothemoretraditionalTheoryofComputationcoursecurrentlytaughtinmostcomputersciencedepartments(andexemplifiedbySipser’sexcellentbookwiththesamename)Weassumeessentiallynocomputationalbackground(thoughaslightexposuretocomputingmayhelp)andverylittlemathematicalbackgroundapartfromtheabilitytounderstandproofsandsomeelementaryprobabilityonfinitesamplespacesAtypicalundergraduatecourseon“DiscreteMath”taughtinmanymathandCSdepartmentsWebdraft:ComplexityTheory:AModernApproachc©SanjeevAroraandBoazBarakReferencesandattributionsarestillincompleteiiiDRAFTivshouldsuffice(togetherwithourAppendix)PartII:Lowerboundsforconcretecomputationalmodels:Thisconcernslowerboundsonresourcesrequiredtosolvealgorithmictasksonconcretemodelssuchascircuits,decisiontrees,etcSuchmodelsmayseematfirstsightverydifferentfromtheTuringmachineusedinPartI,butlookingdeeperonefindsinterestinginterconnectionsPartIII:Advancedtopics:ThisconstitutesthelatterhalfofthebookandislargelydevotedtodevelopmentssincethelatesItincludesaveragecasecomplexity,derandomizationandpseudorandomness,thePCPtheoremandhardnessofapproximation,proofcomplexityandquantumcomputingAppendix:Outlinesmathematicalideasthatmaybeusefulforfollowingcertainchapters,especiallyinPartsIIandIIIAlmosteachchapterinPartsIIandIIIcanbereadinisolationThisisimportantbecausethebookisaimedatmanyclassesofreaders•Physicists,mathematicians,andotherscientistsThisgrouphasbecomeincreasinglyinterestedincomputationalcomplexitytheory,especiallybecauseofhighprofileresultssuchasShor’salgorithmandtherecentdeterministictestforprimalityThisintellectuallysophisticatedgroupwillbeabletoquicklyreadthroughPartIProgressingontoPartsIIandIII,theycanreadindividualchaptersandfindalmosteverythingtheyneedtounderstandcurrentresearch•Computerscientists(eg,algorithmsdesigners)whodonotworkincomplexitytheoryperseTheymayusethebookforselfstudyoreventoteachagraduatecourseorseminarSuchacoursewouldprobablyincludemanytopicsfromPartIandthenasprinklingfromtherestofthebookWeplantoincludeonaseparatewebsitedetailedcourseplanstheycanfollow(eg,iftheyplantoteachanadvancedresultsuchasthePCPTheorem,theymaywishtopreparethestudentsbyteachingotherresultsfirst)•AllthoseprofessorsorstudentswhodoresearchincomplexitytheoryorplantodosoTheymayalreadyknowPartIandusethebookforPartsIIandIII,possiblyinaseminarorreadingcourseThecoverageofadvancedtopicsthereisdetailedenoughtoallowthisWewillprovidesampleteachingplansforsuchseminarsWehopethatthisbookconveysourexcitementaboutthisnewfieldandtheinsightsitprovidesinahostofolderdisciplinesWebdraft:DRAFTContentsAboutthisbookiiiIntroductionIBasicComplexityClassesThecomputationalmodelandwhyitdoesn’tmatterModelingcomputationEncodingsandLanguages:SomeconventionsTheTuringMachineTheexpressivepowerofTuringmachinesTheUniversalTuringMachineDeterministictimeandtheclassPOnthephilosophicalimportanceofPChapternotesandhistoryExercisesNPandNPcompletenessNondeterministicTuringmachinesReducibilityandNPcompletenessTheCookLevinTheorem:ComputationisLocalMorethoughtsontheCookLevintheoremThewebofreductionsInpraiseofreductionsDecisionversussearchcoNP,EXPandNEXPcoNPEXPandNEXPMorethoughtsaboutP,NP,andallthatWebdraft:ComplexityTheory:AModernApproachc©SanjeevAroraandBoazBarakReferencesandattributionsarestillincompletevDRAFTviCONTENTSThephilosophicalimportanceofNPNPandmathematicalproofsWhatifP=NPWhatifNP=coNPChapternotesandhistoryExercisesSpacecomplexityConfigurationgraphsSomespacecomplexityclassesPSPACEcompletenessSavitch’stheoremTheessenceofPSPACE:optimumstrategiesforgameplayingNLcompletenessCertificatedefinitionofNL:readoncecertificatesNL=coNLChapternotesandhistoryExercisesDiagonalizationTimeHierarchyTheoremSpaceHierarchyTheoremNondeterministicTimeHierarchyTheoremLadner’sTheorem:ExistenceofNPintermediateproblemsOraclemachinesandthelimitsofdiagonalizationChapternotesandhistoryExercisesThePolynomialHierarchyandAlternationsTheclassesΣpandΠpThepolynomialhierarchyPropertiesofthepolynomialhierarchyCompleteproblemsforlevelsofPHAlternatingTuringmachinesUnlimitednumberofalternationsTimeversusalternations:timespacetradeoffsforSATDefiningthehierarchyviaoraclemachinesChapternotesandhistoryExercisesWebdraft:DRAFTCONTENTSviiCircuitsBooleancircuitsTuringmachinesthattakeadviceKarpLiptonTheoremCircuitlowerboundsNonuniformhierarchytheoremFinergradationsamongcircuitclassesParallelcomputationandNCPcompletenessCircuitsofexponentialsizeCircuitSatisfiabilityandanalternativeproofoftheCookLevinTheoremChapternotesandhistoryExercisesRandomizedComputationProbabilisticTuringmachinesSomeexamplesofPTMsProbabilisticPrimalityTestingPolynomialidentitytestingTestingforperfectmatchinginabipartitegraphOnesidedandzerosidederror:RP,coRP,ZPPTherobustnessofourdefinitionsRoleofpreciseconstants,errorreductionExpectedrunningtimeversusworstcaserunningtimeAllowingmoregeneralrandomchoicesthanafairrandomcoinBPP⊆PpolyBPPisinPHStateofourknowledgeaboutBPPCompleteproblemsforBPPDoesBPTIMEhaveahierarchytheoremRandomizedreductionsRandomizedspaceboundedcomputationChapternotesandhistoryExercisesComplexityofcountingTheclass#PTheclassPP:decisionproblemanalogfor#PWebdraft:DRAFTviiiCONTENTS#PcompletenessPermanentandValiant’sTheoremApproximatesolutionsto#PproblemsToda’sTheorem:PH⊆P#SATTheclass⊕PandhardnessofsatisfiabilitywithuniquesolutionsTool:PairwiseindependenthashfunctionsProofofTheoremStep:RandomizedreductionfromPHto⊕PStep:MakingthereductiondeterministicOpenProblemsChapternotesandhistoryExercisesInteractiveproofsWarmup:InteractiveproofswithadeterministicverifierTheclassIPProvingthatgraphsarenotisomorphicPubliccoinsandAMSomepropertiesofIPandAMCanGIbeNPcompleteIP=PSPACEArithmetizationInteractiveprotocolfor#SATDSumcheckprotocolProtocolforTQBF:proofofTheoremInteractiveproofforthePermanentTheprotocolThepoweroftheproverProgramCheckingLanguagesthathavecheckersMultiproverinteractiveproofs(MIP)ChapternotesandhistoryExercisesCryptographyHardonaverageproblemsandonewayfunctionsDiscussionofthedefinitionofonewayfunctionRandomselfreducibilityWhatisarandomenoughstringWebdraft:DRAFTCONTENTSixBlumMicaliandYaodefinitionsEquivalenceofthetwodefinitionsOnewayfunctionsandpseudorandomnumbergeneratorsGoldreichLevinhardcorebitPseudorandomnumbergenerationApplicationsPseudorandomfunctionsPrivatekeyencryption:definitionofsecurityDerandomizationTossingcoinsoverthephoneandbitcommitmentSecuremultipartycomputationsLowerboundsformachinelearningRecentdevelopmentsChapternotesandhistoryExercisesIILowerboundsforConcreteComputationalModelsDecisionTreesCertificateComplexityRandomizedDecisionTreesLowerboundsonRandomizedComplexitySometechniquesfordecisiontreelowerboundsComparisontreesandsortinglowerboundsYao’sMinMaxLemmaExercisesChapternotesandhistoryCommunicationComplexityDefinitionLowerboundmethodsFoolingsetThetilinglowerboundRanklowerboundDiscrepancyAtechniqueforupperboundingthediscrepancyComparisonofthelowerboundmethodsMultipartycommunicationcomplexityDiscrepancybasedlowerboundWebdraft:DRAFTxCONTENTSProbabilisticCommunicationComplexityOverviewofothercommunicationmodelsApplicationsofcommunicationcomplexityExercisesChapternotesandhistoryCircuitlowerboundsACandH˚astad’sSwitchingLemmaTheswitchinglemmaProofoftheswitchinglemma(Lemma)CircuitsWith“Counters”:ACCLowerboundsformonotonecircuitsProvingTheoremCliqueIndicatorsApproximationbycliqueindicatorsCircuitcomplexity:ThefrontierCircuitlowerboundsusingdiagonalizationStatusofACCversusPLinearCircuitsWithLogarithmicDepthBranchingProgramsApproachesusingcommunicationcomplexityConnectiontoACCCircuitsConnectiontoLinearSizeLogarithmicDepthCircuitsConnectiontobranchingprogramsKarchmerWigdersoncommunicationgamesanddepthlowerboundsChapternotesandhistoryExercisesAlgebraiccomputationmodelsAlgebraicComputationTreesAlgebraiccircuitsTheBlumShubSmaleModelComplexityClassesovertheComplexNumbersHilbert’sstellensatzDecidabilityQuestions:MandelbrotSetExercisesChapternotesandhistoryWebdraft:DRAFTCONTENTSxiIIIAdvancedtopicsAverageCaseComplexity:Levin’sTheoryDistributionalProblemsFormalizationsof“reallifedistributions”DistNPanditscompleteproblemsPolynomialTimeonAverageReductionsProofsusingthesimplerdefinitionsExistenceofCompleteProblems

用户评价(0)

关闭

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

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

提示

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

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/49

Complexity Theory A Modern Approach draft

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利