极坐标与参数方程(优质课课件)

Laboratoiredel’InformatiqueduParallélismeÉcoleNormaleSupérieuredeLyonUnitéMixtedeRechercheCNRS-INRIA-ENSLYON-UCBLno5668OntheProbabilisticQueryComplexityofTransitivelySymmetricProblemsPascalKoiranVincentNesmeNatachaPortier2006,August30ResearchReportNoRR2006–27ÉcoleNormaleSupérieuredeLyon46Alléed’Italie,69364LyonCedex07,FranceTéléphone:+33(0)4.72.72.80.37Télécopieur:+33(0)4.72.72.80.80Adresseélectronique:[e-mail]yComplexityofTransitivelySymmetricProblemsPascalKoiranVincentNesmeNatachaPortier2006,August30AbstractWeobtainoptimallowerboundsonthenonadaptiveprobabilisticquerycom-plexityofaclassofproblemsdefinedbyaratherweaksymmetrycondition.Infact,foreachprobleminthisclass,givenanumberTofquerieswecomputeexactlytheperformance(i.e.,theprobabilityofsuccessontheworstinstance)ofthebestnonadaptiveprobabilisticalgorithmthatmakesTqueries.Weshowthatthisoptimalperformanceisgivenbyaminimaxformulainvolvingcertainprobabilitydistributions.Moreover,weidentifytwoclassesofproblemsforwhichadaptivitydoesnothelp.Weillustratetheseresultsonafewnaturalexamples,includingunorderedsearch,Simon’sproblem,distinguishingone-to-onefunctionsfromtwo-to-onefunctions,andhiddentranslation.Fortheselastthreeexamples(whichareofparticularinterestinquantumcomputing),therecenttheoremsofAaronson,ofLaplanteandMagniez,andofBar-Yossef,KumarandSivakumarontheprobabilisticcomplexityofblack-boxproblemsdonotyieldanynonconstantlowerbound.Keywords:probabilisticquerycomplexity,lowerbounds,symmetry.R´esum´eNousd´erivonsdesbornesinf´erieuresoptimalessurlacomplexit´eenrequˆetedesalgorithmesprobabilistesnonadaptatifspouruneclassedeprobl`emesd´e-finieparuneconditiondesym´etrieassezfaible.Enr´ealit´e,pourchaquepro-bl`emedecetteclasse,nouscalculonsexactementlaperformanceoptimaled’unalgorithmenonadaptatifdecomplexit´edonn´eeT.Nousmontronsquecetteperformanceoptimaleestdonn´eeparuneformulemin-maxfaisantintervenircertainesdistributionsdeprobabilit´e.Deplus,nousidentifionsdeuxclassesdeprobl`emespourlesquelsl’adaptivit´en’aidepas.Nousillustronscesr´esultatssurquelquesexemplesnaturels,dontlarecherchedansuntableaunontri´e,leprobl`emedeSimon,leprobl`emedelatranslationcach´ee.Pourcertainsdecesexemples,quisontd’unint´erˆetparticulierencalculquantique,lesth´eor`emesr´ecentsd’Aaronson,deLaplanteetMagniez,etdeBar-Yossef,KumarandSivakumarsurlacomplexit´eenrequˆeteprobabilistenedonnentpasmieuxqu’uneborneinf´erieureconstante.Mots-cl´es:complexit´eenrequˆete,algorithmesprobabilistes,sym´etrie,bornesinf´erieures.1IntroductionTherehasbeeninthepastfewyearsasurgeofinterestforlowerboundsintheblack-boxmodel,motivatedinparticularbythestudyofquantumalgorithms.Indeed,sincequantumcircuitlowerboundsseemverydifficulttoobtain,mostoftheknownquantumlowerboundshavebeende-rivedintheblack-boxsetting([11],whichshowshowtosimulateclassicallycertainfamiliesofconstant-depthquantumcircuits,maybeconsideredanexception).Twomethodsprovedpartic-ularlysuccessful:thepolynomialmethodandtheadversarymethod.Wewillnotgiveexhaustivereferenceshere,andwilljustpointout[7]and[2]forthepolynomialmethodaswellas[4]and[24]fortheadversarymethod.Therewasrecentlysomeunexpectedfeedbackfromquantumtoproba-bilisticcomplexity:inspiredbyquantumadversarylowerbounds,Aaronson[1]andLaplanteandMagniez[19]obtainednewlowerboundsonprobabilisticquerycomplexity.Applicationstosort-ing,orderedsearch[19],localsearch[1]andSpernerproblems[13]weregiven.Earlierprobabilisticquerylowerboundswereoftenobtainedbyad-hocarguments.Aspointedoutin[1],withageneralmethodonecanmoreeasily“focusonwhatisuniqueaboutaproblem,andignorewhatiscommonamongmanyproblems”.Liketheirquantumancestors,thelowerboundsof[1,19]areverygeneral(theyapplytoanyblack-boxproblem)andneverthelessgiveoptimalresultsforsomenaturalprob-lems.Theyunfortunatelysufferfromthesamedrawbackastheirancestors,namely,theycannotyieldanynonconstantlowerboundforpromiseproblemssuchthateverypositiveinstanceis“faraway”fromeverynegativeinstance.Notethatthepolynomialmethoddoesnotsufferfromthisdrawback[2,15,16,18].Thecontributionofthispaperistwofold.First,weidentifyaclassofproblems,dubbed“transi-tivelysymmetricproblems”,forwhichoptimallowerboundsonthenonadaptiveprobabilisticquerycomplexitycanbeobtained.Ourlowerboundmethodiscloseinspirittotheadversarymethod.Moreprecisely,foreachprobleminthisclass,givenanumberTofquerieswecomputeexactlytheperformance(i.e.,theprobabilityofsuccessontheworstinstance)ofthebestnonadaptiveprobabilisticalgorithmthatmakesTqueries.Weshowthatthisoptimalperformanceisgivenbyaminimaxformulainvolvingcertainprobabilitydistributions.Aprecisedefinitionoftheclassoftransitivelysymmetricproblemsisgivenatthebeginningofsection3.Theideaisthattheauto-morphismgroupoftheproblemmustacttransitivelyonthesetofpositiveinstancesaswellasonthesetofnegativeinstances.Theelementsoftheautomorphismgroupactbypermutationsonthedomainoftheblack-boxfunctionandbypermutationsonitsrange.Forinstance,whenarbitrarypermutationsonthedomainbutnopermutationoftherange(excepttheidentity)areallowedtheusualnotionofsymmetricfunctionisr