搜索
TheRoleofRelativizationinComplexityTheoryLanceFortnow UniversityofChicagoDepartmentofComputerScience1100East58thStreetChicago,Illinois60637AbstractSeveralrecentnonrelativizingresultsintheareaofinteractiveproofshavecausedmanypeopletoreviewtheimportanceofrelativization.Inthispaperwetakealookathowcomplexitytheoristsuseandmisuseoracleresults.Wepayspecialattentiontothenewinteractiveproofsystemsandprogramcheckingresultsandtrytounderstandwhytheydonotrelativize.Wegivesomenewresultsthatmayhelpustounderstandthesequestionsbetter.1IntroductionTherecentresultIP=PSPACE[LFKN92,Sha92]surprisedthetheoreticalcomputersciencecommunityinmorewaysthanone.Afewyearsearlier,FortnowandSipser[FS88]createdanoraclerelativetowhichco-NPdidnothaveinteractiveproofs.TheIP=PSPACEresultwashonestlyanonrelativizingtheorem.Severalquestionsimmediatelypoppedup:Whydidn’tthisresultrelativize?Whatspeci ctechniqueswereusedthatavoidedrelativization?Howcanweusethesetechniquestoproveothernonrelativizingfacts?Alsomucholderquestionsresurfaced:Whatexactlytooracleresultsmean?Whatshouldweinfer,ifanything,fromarelativization?Suchquestionsgainedevenmoreimportancewhenwediscoveredtheamazingpowerofmul-tipleproverinteractiveproofsystems[BFL91],transparentproofs[BFLS91]andprobabilisticallycheckableproofs[AS92,ALM+92].Wemaynot ndsatisfactoryanswerstothesequestionsinthenearfuture.However,inthispaperwewillgivesomeintuitionandsometheoremsaboutoraclesthatmayhelpshedlightonsomeoftheseissues.InSection3,wewillseethatrelativizationisanextremelypowerfultoolinhelpingcomplexitytheoristsdirecttheirresearch.InSection4,wewilllookatearlyresultsofprovablestatementswithnegativerelativization.Wewilllookatthesevariousexamplesandarguethattheyalllackaproperoracleaccessmechanism.Insection5,wetakeacloselookatthenewunrelativizingresultsforinteractiveproofsystems.Weprovesomenewresultsthatmayhelpusunderstandtheseissuesbetter.Wealsoarguethatthe Email:fortnow@cs.uchicago.edu.PartiallysupportedbyNSFgrantCCR92-53582.1newinteractiveproofsystemtechniquesdonotrelativizebecausetheytakeadvantageofcertainalgebraicpropertiesofcomplexityclasses.Insection5.1welookatwhathappenswhenweaddanoracletoprobabilisticallycheckableproofs(PCP).Arora,Lund,Motwani,SudanandSzegedy[ALM+92]showthateverylanguageinNPhasaPCPusingonlyalogarithmicnumberofrandomcointossesandaconstantnumberofqueriestotheproof.Weshowthatinarelativizedworld,forallk,sucharesultdoesnotholdevenifweallowtheveri ertouseapolynomialnumberofrandombitsandnkproofqueries(Theorem5.2).AlthoughHeller[Hel81]hascreatedanoracleArelativetowhichNPA=EXPA,weshowthatPCPA(logn;1)=EXPAwouldimplythatP6=NP(Theorem5.4).Thus ndingsuchanoraclewouldbeashardassettlingtheP=NPquestion.Arora,ImpagliazzoandVazirani[AIV92]arguethatthe\local-checkabilitypropertyofcom-plexityclassesisamajorreasonthattheresultsoninteractiveproofsdonotrelativize.InSec-tion5.2,wegivenegativeevidenceforthisthesisbyshowingthatunderareasonableaccessmech-anism,localcheckabilitydoesinfactrelativize.Wegivesupportinsteadtothethesisthatitisthealgebraicpropertiesofcomplexityclassesthatdonotrelativize.InSection5.3,wegiveevidenceforthispropositionbyshowingthatIP=PSPACEholdsrelativetoalgebraicextensionsofarbitrarilycomplicatedlanguages.Finally,inSection6,wegiveabriefarguementagainstinferinganyinformationfromrandomoracleresults.Wearguethatweshouldonlyuserandomoraclesasatooltocombineoracleconstructions.However,webelievethatgenericoraclesareamuchstrongerandsharpertoolforthispurpose.CaveatsThispapercontainsseveralopinionsontheuseandmisuseofrelativizationresults.Wemustcautionthereaderthatothercomplexitytheoristsmayhavedi eringopinionsonthesematters.Inthispaper,wehavetriedtogiveseveralexamplestoillustratevariouspoints.Howeverthispaperisnotmeanttobeasurveypaper.Manyimportantworksintheareahavenotbeenmentionedduetolackofspace.2NotationandDe nitionsMostofthenotationandde nitionsfollowfromthestandardtextbooksonthe eld[HU79,GJ79].Weuse torepresentthejoinoftwosetsAandB,i.e.,A B=(f0g A)[(f1g B).WeuseFPtorepresentthepolynomial-timecomputablefunctions.ItisamisnomertorelativizeacomplexityclassC.InsteadsupposewetakeanenumerationofmachinesforCandgivethemsomeaccessmechanismtoanoraclesetA.WethensaytherelativizedclassCAconsistsofthelanguagesrecognizedbytheacceptancecriteriaforCappliedtothemachinesusingtheoracleA.Ofcoursethisde nitionmaydependgreatlyonthespeci cenumerationofthemachinesofCaswellastheoracleaccessmechanism.TheusualaccessmechanismconsistsofaseparateoracletapethattheTuringmachinecanwritedownqueriesandlearntheanswers.However,asweshallseeinSections4and5.2,suchmodelsmayundulyhandicapthemachines.22.1RelativizingFormulaeItwillbeusefultohaverelativizedNP-completeandPSPACE-completesets.Letarelativized3CNFformulabeaCNFformulawithclausesoftheform:xi1_xi2_xi3_A(xj1;:::;xjk)whereA(xj1;:::;xjk)istrueifxj1:::xjkisinA.AnyofthevariablesortheA(xj1;:::;xjk)termmaybenegated.Lemma2.1Let Abearelativized3CNFformulaoveranoracleA.LetAbeaclosedrelativized3CNFformulawitharbitrary rst-orderexistentialanduniversalquanti ersoverthevariables.1.Determiningw