资源描述：
《goldreich o. introduction to complexity theory (lecture notes 1999)(375s)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、IntroductiontoComplexityTheory{LectureNotesOdedGoldreichDepartmentofComputerScienceandAppliedMathematicsWeizmannInstituteofScience,Israel.Email:oded@wisdom.weizmann.ac.ilJuly31,1999IcCopyright1999byOdedGoldreich.Permissiontomakecopiesofpartorallofthisworkforp
2、ersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro torcommercialadvantageandthatnewcopiesbearthisnoticeandthefullcitationonthe rstpage.Abstractingwithcreditispermitted.IIPrefaceComplexityTheoryisacentral eldofTheoreticalCo
3、mputerScience,witharemarkablelistofcelebratedachievementsaswellasaveryvibrantpresentresearchactivity.The eldisconcernedwiththestudyoftheintrinsiccomplexityofcomputationaltasks,andthisstudytendtoaimatgenerality:Itfocusesonnaturalcomputationalresources,andthee
4、ectoflimitingthoseontheclassofproblemsthatcanbesolved.Theselecturenotesweretakenbystudentsattendingmyyear-longintroductorycourseonComplexityTheory,givenin1998{99attheWeizmannInstituteofScience.Thecoursewasaimedatexposingthestudentstothebasicresultsandresearch
5、directionsinthe eld.Thefocuswasonconceptsandideas,andcomplextechnicalproofswereavoided.Speci ctopicsincluded:RevisitingNPandNPC(withemphasisonsearchvsdecision);Complexityclassesde nedbyoneresource-bound{hierarchies,gaps,etc;Non-deterministicSpacecomplexity
6、(withemphasisonNL);RandomizedComputations(e.g.,ZPP,RPandBPP);Non-uniformcomplexity(e.g.,P/poly,andlowerboundsonrestrictedcircuitclasses);ThePolynomial-timeHierarchy;Thecountingclass#P,approximate-#PanduniqueSAT;Probabilisticproofsystems(i.e.,IP,PCPandZK)
7、;Pseudorandomness(generatorsandderandomization);TimeversusSpace(inTuringMachines);Circuit-depthversusTM-space(e.g.,AC,NC,SC);Average-casecomplexity;Itwasassumedthatstudentshavetakenacourseincomputability,andhencearefamiliarwithTuringMachines.Mostofthepres
8、entedmaterialisquiteindependentofthespeci c(reasonable)modelofcom-putation,butsome(e.g.,Lectures5,16,and19{20)dependsheavilyonthelocalityofcomputationofTuringmachines.IIIIVStateofthesenot
