Computational Complexity A Modern Approach - Sanjeev Arora

《Computational Complexity A Modern Approach - Sanjeev Arora》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、winxos11-01-28winxos11-01-28iComputationalComplexity:AModernApproachDraftofabook:DatedAugust2006Commentswelcome!SanjeevAroraandBoazBarakPrincetonUniversitycomplexitybook@gmail.comNottobereproducedordistributedwithouttheauthor’spermissionSomechaptersaremorefinishedthanothers.Referencesan

2、dattributionsareverypreliminaryandweapologizeinadvanceforanyomissions(buthopeyouwillneverthelesspointthemouttous).DRAFTiiDRAFTAboutthisbookComputationalcomplexitytheoryhasdevelopedrapidlyinthepastthreedecades.Thelistofsurprisingandfundamentalresultsprovedsince1990alonecouldfillabook:the

3、seincludenewprobabilisticdefinitionsofclassi-calcomplexityclasses(IP=PSPACEandthePCPTheorems)andtheirimplicationsforthefieldofapproximationalgorithms;Shor’salgorithmtofactorintegersusingaquantumcomputer;anunderstandingofwhycurrentapproachestothefamousPversusNPwillnotbesuccessful;atheoryo

4、fde-randomizationandpseudorandomnessbaseduponcomputationalhardness;andbeautifulconstructionsofpseudorandomobjectssuchasextractorsandexpanders.Thisbookaimstodescribesuchrecentachievementsofcomplexitythe-oryinthecontextoftheclassicalresults.Itisintendedtobeatextandaswellasareferenceforse

5、lf-study.Thismeansitmustsimultaneouslycatertomanyaudiences,anditiscarefullydesignedwiththatgoal.Through-outthebookweexplainthecontextinwhichacertainnotionisuseful,andwhythingsaredefinedinacertainway.Examplesandsolvedexercisesaccompanykeydefinitions.Thebookhasthreepartsandanappendix.PartI

6、:Basiccomplexityclasses:Thispartprovidesabroadintroduc-tiontothefieldandcoversbasicallythesamegroundasPapadim-itriou’stextfromtheearly1990s—butmorequickly.Itmaybesuit-ableforanundergraduatecoursethatisanalternativetothemoretraditionalTheoryofComputationcoursecurrentlytaughtinmostcompute

7、rsciencedepartments(andexemplifiedbySipser’sexcellentbookwiththesamename).Weassumeessentiallynocomputationalbackground(thoughaslightexposuretocomputingmayhelp)andverylittlemathematicalback-groundapartfromtheabilitytounderstandproofsandsomeelemen-taryprobabilityonfinitesamplespaces.Atyp