Computational Complexity A Conceptual Perspective

ComputationalComplexity:AConceptualPerspectiveOdedGoldreichDepartmentofComputerScienceandAppliedMathematicsWeizmannInstituteofScience,Rehovot,Israel.Workingdraft(January2006)ItoDanacCopyright2006byOdedGoldreich.Permissiontomakecopiesofpartorallofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcom-mercialadvantageandthatnewcopiesbearthisnoticeandthefullcitationontherstpage.Abstractingwithcreditispermitted.IIPrefaceThestriveforeciencyisancientanduniversal,astimeandotherresourcesarealwaysinshortage.Thus,thequestionofwhichtaskscanbeperformedecientlyiscentraltothehumanexperience.Akeysteptowardsthesystematicstudyoftheaforementionedquestionisarigorousdenitionofthenotionofataskandofproceduresforsolvingtasks.Thesedenitionswereprovidedbycomputabilitytheory,whichemergedinthe1930’s.Thistheoryfocusesoncomputationaltasks,andconsidersautomatedprocedures(i.e.,computingdevicesandalgorithms)thatmaysolvesuchtasks.Infocusingattentiononcomputationaltasksandalgorithms,computabilitytheoryhassetthestageforthestudyofthecomputationalresources(liketime)thatarerequiredbysuchalgorithms.Whenthisstudyfocusesontheresourcesthatarenecessaryforanyalgorithmthatsolvesaparticulartask(orclassoftasks),thestudybecomespartofthetheoryofComputationalComplexity(alsoknownasComplexityTheory).1ComplexityTheoryisacentraleldofthetheoreticalfoundationsofComputerScience.Itisconcernedwiththestudyoftheintrinsiccomplexityofcomputationaltasks.Thatis,atypicalComplexitytheoreticstudylooksatthecomputationalresourcesrequiredtosolveaacomputationaltask(oraclassofsuchtasks),ratherthanataspecicalgorithmoralgorithmicscheme.Actually,researchinComplex-ityTheorytendstostartwithandfocusonthecomputationalresourcesthemselves,andaddressestheeectoflimitingtheseresourcesontheclassoftasksthatcanbesolved.Thus,ComputationalComplexityisthestudyofthewhatcanbeachievedwithinlimitedtime(and/orotherlimitednaturalcomputationalresources).The(half-century)historyofComplexityTheoryhaswitnessedtwomainre-searcheorts(ordirections).Therstdirectionisaimedtowardsactuallyestab-lishingconcretelowerboundsonthecomplexityofproblems,viaananalysisoftheevolutionoftheprocessofcomputation.Thus,inasense,theheartofthisdirectionisa\low-levelanalysisofcomputation.Mostresearchincircuitcom-plexityandinproofcomplexityfallswithinthiscategory.Incontrast,asecond1Incontrast,whenthefocusisonthedesignandanalysisofspecicalgorithms(ratherthanontheintrinsiccomplexityofthetask),thestudybecomespartofarelatedsubeldthatmaybecalledAlgorithmicDesignandAnalysis.Furthermore,AlgorithmicDesignandAnalysistendstobesub-dividedaccordingtothedomainofmathematics,scienceandengineeringinwhichthecomputationaltasksarise.Incontrast,ComplexityTheorytypicallymaintainsaunityofthestudyoftaskssolveablewithincertainresources(regardlessoftheoriginsofthesetasks).IIIIVresearcheortisaimedatexploringtheconnectionsamongcomputationalprob-lemsandnotions,withoutbeingabletoprovideabsolutestatementsregardingtheindividualproblemsornotions.Thiseortmaybeviewedasa\high-levelstudyofcomputation.ThetheoryofNP-completenessaswellasthestudiesofapprox-imation,probabilisticproofsystems,pseudorandomnessandcryptographyallfallwithinthiscategory.Thecurrentbookfocusesonthelattereort(ordirection).Welistseveralrea-sonsforourdecisiontofocusonthe\high-leveldirection.Therstisthegreatconceptualsignicanceoftheknownresults;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.Thisbookoersaconceptualperspectiveoncomplexitytheory,andthepresen-tationisdesignedtohighlightthisperspective.Itisintendedmainlyforstudentsthatwishtolearncomplexitytheoryandforeducatorsthatintendtoteachacourseoncomplexitytheory.Thebookisalsointendedtopromoteinterestincomplexitytheoryandmakeitacccessibletogeneralreaderswithadequatebackground(whichismainlybeingcomfortablewithabstractdiscussions,denitionsandproofs).Weexpectmostreaderstohaveabasicknowledgeofalgorithms,oratleastbefairlycomfortablewiththenotionofanalgorithm.Thebookfocusesonseveralsub-areasofcomplexitytheory(seethefollowingorganizationandchaptersummaries).Ineachcase,theexpositionstartsfromtheintuitivequestionsaddressesbythesub-area,asembodiedintheconceptsthatitstudies.Theexpositiondiscussesthefundament