资源描述：
《normal numbers and sources for bpp》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、NormalNumbersandSourcesforBPPMartinStraussDepartmentofComputerScienceIowaStateUniversityAmes,IA50011-1040mstrauss@cs.iastate.eduAbstractIn[10],Lutzproposedanotionofsource,anonrandomsequencethatcansubstituteinacertainwayfortherandombitsusedbybounded-erro
2、rprobabilisticmachines.HeshowedthatalmosteverysequenceinpolynomialDSPACE(2)isasource.WeimprovethisabundanceresulttoPSPACE,by rstshowingthatthesourcesareexactlytheclassicalnormalnumbers(ornormalsequences)ofBorel.TherearesequencesclearlyinPthathavelongbeen
3、knowntobenormal,andwegoontoshowthere0aresourcesinAC:Thissuggeststhatalternatenotionsofsourceshouldbeexplored.1IntroductionIn[10],Lutzexaminesaparticularkindofpseudorandomnessusefulforsimulat-ingthebounded-errorprobabilisticmachines.Thepseudorandomnessisn
4、otintheformofagenerator,thatexpandsashorttrulyrandomstring,butinsteadisasinglecomputablesequence,calledasource,whoseelementscansubstituteforrandombitsinarepeatedsimulationofeverybounded-errormachine.Thusasourceisaparticularsequencethatisrandomenough"ina
5、quanti ableway.Lutz'sworkcapturestwointuitivepropertiesofsources.Intuitively,sourcesareuniversal,i.e.,asinglesourceshouldworkforallmachinesandallinputs,andsourcesareabundant,i.e.,almostallsequencesshouldbesources.Uni-versalityisbuiltintothede nitionofsou
6、rce(seebelow),whileabundanceisataparticularlevelofresourceboundedness
7、almosteverysequenceinpolynomialESPACE=DSPACE(2)isshowntobeasource.Lutzalsotrades2ResearchsupportedbyNSFgrantsCCR-9204874andCCR-9157382.Apreliminaryver-sionofthispaperappearedinthe1995
8、SymposiumonTheoreticalAspectsofComputerScience.1someuniversalityforabundance,showingthatforanyonemachine,almostalllinearsequencesinESPACE=DSPACE(2)are,forallinputs,sources.WhileLutzwasprimarilyinterestedintheBPPmachines,henotesthattheresultsholdforallbou
9、ndederrormachines,i.e.,almosteverysequenceinESPACEcanreplacearandomsequenceforbounded-errormachinesof2arbitrarycomplexity.ThissuggeststhatthecomplexityofasequenceShaslittletodowiththecomplexityoflanguageshavingmachinesforw
