Computational Complexity A Conceptual Perspective - Oded Goldreich

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

1、winxos11-01-28winxos11-01-28ComputationalComplexity:AConceptualPerspectiveOdedGoldreichDepartmentofComputerScienceandAppliedMathematicsWeizmannInstituteofScience,Rehovot,Israel.December12,2006ItoDanacCopyright2006byOdedGoldreich.Permissiontomakecopiesofpartorallof

2、thisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcom-mercialadvantageandthatnewcopiesbearthisnoticeandthefullcitationontherstpage.Abstractingwithcreditispermitted.IIPrefaceThestriveforeciencyisancientandunive

3、rsal,astimeandotherresourcesarealwaysinshortage.Thus,thequestionofwhichtaskscanbeperformedecientlyiscentraltothehumanexperience.Akeysteptowardsthesystematicstudyoftheaforementionedquestionisarigorousdenitionofthenotionofataskandofproceduresforsolvingtasks.Thesed

4、enitionswereprovidedbycomputabilitytheory,whichemergedinthe1930's.Thistheoryfocusesoncomputationaltasks,andconsidersautomatedprocedures(i.e.,computingdevicesandalgorithms)thatmaysolvesuchtasks.Infocusingattentiononcomputationaltasksandalgorithms,computabilitytheo

5、ryhassetthestageforthestudyofthecomputationalresources(liketime)thatarerequiredbysuchalgorithms.Whenthisstudyfocusesontheresourcesthatarenecessaryforanyalgorithmthatsolvesaparticulartask(orataskofaparticulartype),thestudybecomespartofthetheoryofComputationalComple

6、xity(also1knownasComplexityTheory).ComplexityTheoryisacentraleldofthetheoreticalfoundationsofComputerScience.Itisconcernedwiththestudyoftheintrinsiccomplexityofcomputationaltasks.Thatis,atypicalComplexitytheoreticstudylooksatthecomputationalre-sourcesrequiredtoso

7、lveacomputationaltask(oraclassofsuchtasks),ratherthanataspecicalgorithmoranalgorithmicschema.Actually,researchinComplexityTheorytendstostartwithandfocusonthecomputationalresourcesthemselves,andaddressestheeectoflimitingtheseresourcesontheclassoftasksthatcanbesol

8、ved.Thus,ComputationalComplexityisthestudyofthewhatcanbeachievedwithinlimitedtime(and/orotherlimitednaturalcomputationalresources).The(half-century)hist