您好,欢迎访问三七文档
ComputationalComplexity:AConceptualPerspectiveOdedGoldreichDepartmentofComputerScienceandAppliedMathematicsWeizmannInstituteofScience,Rehovot,Israel.Workingdraft(January2006)ItoDanac Copyright2006byOdedGoldreich.Permissiontomakecopiesofpartorallofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro torcom-mercialadvantageandthatnewcopiesbearthisnoticeandthefullcitationonthe rstpage.Abstractingwithcreditispermitted.IIPrefaceThestrivefore ciencyisancientanduniversal,astimeandotherresourcesarealwaysinshortage.Thus,thequestionofwhichtaskscanbeperformede cientlyiscentraltothehumanexperience.Akeysteptowardsthesystematicstudyoftheaforementionedquestionisarigorousde nitionofthenotionofataskandofproceduresforsolvingtasks.Thesede nitionswereprovidedbycomputabilitytheory,whichemergedinthe1930’s.Thistheoryfocusesoncomputationaltasks,andconsidersautomatedprocedures(i.e.,computingdevicesandalgorithms)thatmaysolvesuchtasks.Infocusingattentiononcomputationaltasksandalgorithms,computabilitytheoryhassetthestageforthestudyofthecomputationalresources(liketime)thatarerequiredbysuchalgorithms.Whenthisstudyfocusesontheresourcesthatarenecessaryforanyalgorithmthatsolvesaparticulartask(orclassoftasks),thestudybecomespartofthetheoryofComputationalComplexity(alsoknownasComplexityTheory).1ComplexityTheoryisacentral eldofthetheoreticalfoundationsofComputerScience.Itisconcernedwiththestudyoftheintrinsiccomplexityofcomputationaltasks.Thatis,atypicalComplexitytheoreticstudylooksatthecomputationalresourcesrequiredtosolveaacomputationaltask(oraclassofsuchtasks),ratherthanataspeci calgorithmoralgorithmicscheme.Actually,researchinComplex-ityTheorytendstostartwithandfocusonthecomputationalresourcesthemselves,andaddressesthee ectoflimitingtheseresourcesontheclassoftasksthatcanbesolved.Thus,ComputationalComplexityisthestudyofthewhatcanbeachievedwithinlimitedtime(and/orotherlimitednaturalcomputationalresources).The(half-century)historyofComplexityTheoryhaswitnessedtwomainre-searche orts(ordirections).The rstdirectionisaimedtowardsactuallyestab-lishingconcretelowerboundsonthecomplexityofproblems,viaananalysisoftheevolutionoftheprocessofcomputation.Thus,inasense,theheartofthisdirectionisa\low-levelanalysisofcomputation.Mostresearchincircuitcom-plexityandinproofcomplexityfallswithinthiscategory.Incontrast,asecond1Incontrast,whenthefocusisonthedesignandanalysisofspeci calgorithms(ratherthanontheintrinsiccomplexityofthetask),thestudybecomespartofarelatedsub eldthatmaybecalledAlgorithmicDesignandAnalysis.Furthermore,AlgorithmicDesignandAnalysistendstobesub-dividedaccordingtothedomainofmathematics,scienceandengineeringinwhichthecomputationaltasksarise.Incontrast,ComplexityTheorytypicallymaintainsaunityofthestudyoftaskssolveablewithincertainresources(regardlessoftheoriginsofthesetasks).IIIIVresearche ortisaimedatexploringtheconnectionsamongcomputationalprob-lemsandnotions,withoutbeingabletoprovideabsolutestatementsregardingtheindividualproblemsornotions.Thise ortmaybeviewedasa\high-levelstudyofcomputation.ThetheoryofNP-completenessaswellasthestudiesofapprox-imation,probabilisticproofsystems,pseudorandomnessandcryptographyallfallwithinthiscategory.Thecurrentbookfocusesonthelattere ort(ordirection).Welistseveralrea-sonsforourdecisiontofocusonthe\high-leveldirection.The rstisthegreatconceptualsigni canceoftheknownresults;thatis,manyknownresults(aswellasopenproblems)inthisdirectionhaveanextremelyappealingconceptualmes-sage,whichcanalsobeappreciatedbynon-experts.Furthermore,theseconceptualaspectsmaybeexplainedwithoutenteringintoexcessivetechnicaldetail.Conse-quently,the\high-leveldirectionismoresuitableforanexpositioninabookofthecurrentnature.Finally,thereisasubjectivereason:the\high-leveldirec-tioniswithinourownexpertise,whilethiscannotbesaidaboutthe\low-leveldirection.Thelastparagraphbringsustoadiscussionofthenatureofthecurrentbook,whichiscapturedbythesubtitle(i.e.,\aconceptualperspective).Ourmainthesisisthatcomplexitytheoryisextremelyrichinconceptualcontent,andthatthiscontentsshouldbeexplicitlycommunicatedinexpositionsandcoursesonthesubject.Thedesiretoprovideacorrespondingtextbookisindeedthemotivationforwritingthecurrentbookanditsmaingoverningprinciple.Thisbooko ersaconceptualperspectiveoncomplexitytheory,andthepresen-tationisdesignedtohighlightthisperspective.Itisintendedmainlyforstudentsthatwishtolearncomplexitytheoryandforeducatorsthatintendtoteachacourseoncomplexitytheory.Thebookisalsointendedtopromoteinterestincomplexitytheoryandmakeitacccessibletogeneralreaderswithadequatebackground(whichismainlybeingcomfortablewithabstractdiscussions,de nitionsandproofs).Weexpectmostreaderstohaveabasicknowledgeofalgorithms,oratleastbefairlycomfortablewiththenotionofanalgorithm.Thebookfocusesonseveralsub-areasofcomplexitytheory(seethefollowingorganizationandchaptersummaries).Ineachcase,theexpositionstartsfromtheintuitivequestionsaddressesbythesub-area,asembodiedintheconceptsthatitstudies.Theexpositiondiscussesthefundament
本文标题:Computational Complexity A Conceptual Perspective
链接地址:https://www.777doc.com/doc-6439405 .html