资源描述：
《bi-immunity results for cheatable sets》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Bi-immunityResultsforCheatableSetsRichardBeigelDepartmentofComputerScienceTheJohnsHopkinsUniversityBaltimore,MD21218January5,1995AbstractAnoracleAisk-cheatableifthereisapolynomial-timealgorithmktodeterminetheanswersto2parallelqueriestoAfromtheanswerstoonlykqueriestosomeotheroracleB
2、.Itisknownthat1-cheatablesetscannotbebi-immuneforP.Incontrast,weconstruct2-cheatablesetsthatarebi-immuneforarbitrarytimecomplexityclasses.Inad-dition,foreachk,weconstructasetthatis(k+1)-cheatable,butnotk-cheatable;weshowthatthisseparationdoesnotholdwithbi-immunity.Weshowthatifarecur
3、sivesetAisbi-immuneforPthenthereexistsanin nite1-cheatablesetthatispolynomial-timem-reducibletoA.ConsequentlyifNPcontainsasetthatisbi-immuneforPthenNPcontainsasetthatisnotpolynomial-timeTuring-equivalenttoaself-reducibleset.1.IntroductionComplexitytheorydealswithhowhardproblemsare.T
4、ime,space,andal-ternationhaveservedasmeasuresofdiculty.Recently,researchershaveResearchsupportedbyaFannieandJohnHertzFoundationfellowshipandbyNSFgrantCCR-8808949.PartofthisworkwasdonewhiletheauthorwasagraduatestudentatStanfordUniversity.1lookedatthenumberofqueriesthatmustbemadetoa
5、noraclebyapoly-nomialtimealgorithmthatsolvesaproblem,asameasureofthatproblem'sdiculty[15,24].Whenweconsidernumber-of-queriesasacomplexitymea-sure,itisnaturaltoconsiderthecomplexityclasses"offunctionsandsetsinducedbythatmeasure.Wecallthesecomplexityclassesboundedqueryclasses,becaus
6、etheycontainsetsandfunctionscomputablebyalgorithmsthatmakeaboundednumberofqueriestoanoracle.Sincenumber-of-queriesisnotacomplexitymeasureinthesenseofBlum,manyexpectedresultsaboutcomplexitymeasuresdonotapplytoboundedqueryclasses.Severalpapers[1,2,9,7,4,5,?]investigatetherelationships
7、amongdif-ferentboundedqueryclasses.OnebasicquestionisWhendokqueriestoanoracleenableustocomputemorefunctionsinpolynomialtimethanonlyk?1queries?"Thebasicquestionintheprecedingparagraphhasatleastsixteeninter-pretations.QueriesmaybemadeinseriesasinaTuringreduction(serialquerieshavealso
8、beencalledadaptive
