on the bpp hierarchy problem

《on the bpp hierarchy problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ONTHEBPPHIERARCHYPROBLEMCHRISTERBERGANDJOHANH?STADAbstract.InthispaperwegiveargumentsbothforandagainsttheexistenceofanoracleA,relativetowhichBPPequalsprobabilisticlineartime.First,weproveastructuretheoremforprobabilisticoraclemachines,whichsaysthateitherwecanxthe

2、outputofthemachinebysettingtheanswertoonlypolynomiallymanyoraclestrings,orelsewecansetpartoftheoraclesuchthatthemachinebecomesimproper.ThistheoremcouldhelpcompletetheconstructionoftheoracleA,whichwasproposedbyFortnowandSipserin[2].Second,weshowthatthereareprevious

3、lyunknownproblemswiththisconstruction.Thusthequestionwhetherprobabilisticpolynomialtimehasahierarchyrelativetoalloraclesremainscompletelyopen.1.IntroductionkIfweareabletosolveaprobleminpolynomialtimenforsomek,itisnaturaltoaskifitispossibletosolvethesameproblemfast

4、er,forexamplek?1intimen.Eventhoughformostproblemswendthatthereissomelimitastohowfastanalgorithmweareabletodesign,wealsoknowthatitisveryhardtoprovethatouralgorithmisthebestpossible.However,fordeterministicandnon-deterministicpolynomialtimeatleastweknowthattheredoe

5、xistproblems(althoughtheyaresomewhatunnatural)whichkk?1aresolvableintimenbutnotintimenandhence,thesecomplexityclassescontainsahierarchyofincreasinglymoredicultproblems.Thehistoryofthesehierarchytheoremsisasoldascomplexitytheoryitselfthatdeterministicpolynomialti

6、mehasahierarchywasshownbyHartmanisandStearns[5]in1965andthecorrespondingtheoremfornon-deterministictimewasshownbyCook[1]1973.ThecomplexityclassBPPconsistsofproblemssolvableinpolynomialtimebyprobabilisticTuringmachineswhichforeachinputacceptswithprobabilityeitherle

7、ssthan1=3orgreaterthan2=3.Althoughitisnaturaltosuspectthatalsothiscomplexityclasscontainsahierarchyofproblems,thishasnotbeenprovedtobethecase.Thetechniquesthatworkfordeter-ministicandnon-deterministictimedonotapplyintheprobabilisticcase.Itisnotcompletelyclearwhypr

8、obabilistictimeisdierentinthisrespect,butonemajorobstacleistheexistenceofimpropermachines.Namely,ifforsomeinputamachineacceptswithprobabilitybetween1=3