//img.uscri.be/pth/e0b0e2918f1f45b2d5f48d1afaf72f879deb94f7
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Reductions parametriques La W hierarchie Deux exemples L'hypothese de complexite exponentielle ETH

De
75 pages
Reductions parametriques La W -hierarchie. Deux exemples L'hypothese de complexite exponentielle (ETH) Complexite parametree (3) Reductions parametrees et classes de complexite Christophe PAUL (CNRS - LIRMM) November 5, 2010 Christophe PAUL (CNRS - LIRMM) Complexite parametree (3) Reductions parametrees et classes de complexite

  • alphabet fini

  • ?? ?

  • complexite

  • fpt

  • ??

  • parametres sur les alphabets respectifs

  • hypothese de complexite exponentielle

  • classe de complexite fpt

  • reductions parametrees

  • parametrisation de ??


Voir plus Voir moins
R´eductionspara´mteiruqseaL-Wihra´ehircDee.exuxlpmeseAUL(phePistoChrlpmoC)MMRIL-SRNCr´etm´rapa´eitexarapte´mee´rctes(3ee´e)Rctdunsio´te
Christophe PAUL (CNRS - LIRMM)
Complexit´eparame´tre´e(3) Re´ductionsparametr´eesetclassesdecomplexite´ ´
November 5, 2010
lassesdecomplexi
´tixelpmoC)MMRIL3)e(´etr´eamarephCirNRS-UL(ChePAstoptixe
Re´ductionsparame´triques Rappelsetd´enitions Exemples
e´cedslpmo
2
Deux exemples Ensembleind´ependant Ensemble dominant
1
LaW-harchi´erei. Circuits logiques weighted-sat
4
3
Lhypothe`sedecomplexite´exponentielle(ETH)
nopsrama´Rdecuitetclasse´etr´eesitcude´RmarapsnohceireraexexD.ueique´etr-hi´sLaWelpmstd´enitRappelseselpmexEsnoi
κ)tee(Q,pairtunetsnuteeκQΣqleuioatistr´eamareputseΣxis.Σedneml`arepUn2obprrus(se)Σe´mae´rtQ(κ,e`emPF(Te)tsdParFixeerizametatcarTdelis)elbunteisexthrigoalennitsnaeced,Q(κx)estsonparam`etC.erssalcedelpmoitexFP´enpTUblro´rte´marape´tixeplom)CMMIR-LRSCNesct´ree´mteaparionsduct)R´eee(3elpm´tixtnodocalideceteQAqmed´uihpPeUA(LC)rhsiotx)).nO(1eestf(κ(et´
Proble`meparame´tre´ Soit Σ un alphabet fini. 1Unearptaoinmae´rtside Σest une fonctionκ: ΣN calculable en temps polynomial.
ssaledsepmocixel´Ritnodecueuxexemplesh-Ware´ihcraD.eiarsp´eamiqtrsLueesmelpsnxEtioie´ntdseelppRa
ssseedocpmelix´tram´etr´eesetcla
Probl`emeparametre´ ´ Soit Σ un alphabet fini. 1Unepamarnoirte´taside Σest une fonctionκ: ΣN calculable en temps polynomial. 2Unerte´l`obpramarepem(sur Σ) est une paire (Q, κ) tel que ´ QΣetκtsepenuamartr´eatisndioeΣ.
sixΣest une instance deQ,κ(x).etreram`onpaests
e
Classe de complexite FPT ´ Unprobl`eme(Q, κ) estFPT(Fixed Parameterized Tractable) s il existe un algorithmeAecd´uiqeidQstdoetocpmtnal´teeelix
f(κ(x)).nO(1)
tr´eamaraWsLueiqde´Rpsnoitcumplexexesrerah-´iD.uehcei´etdseelppRaselpmexEsnoitin(3)R´eductionspatie´apar´mte´ree-LRSMMIRom)CexplsirhhpotUAPeNC(LC
selpedR´tiucpsnomararte´euqisLaW-hi´erarchieD.ueexexpmelselseRappntidte´xEmeoisnunteisexIl)3(1|Ox|.))x(κ(fe´tixeompl)dect`aκpporraarTPp(mhFerotix)κ()x)R(g()6Σx(0κ,ruoptuottellequebleg:NNcnlaucalfenotcoiluclelbaurapglanRe2castCNRSAUL(MM)C-LIRxetimolpar´me´aprhCPehpotsisetclassesdecompelix´te
On notera(Q, κ)6fpt(Q0, κ0)
De´nition:R´eductionparam´etrique Soient (Q, κ) et (Q0, κ0te´marapseme`lboesrlsuesr´)deuxpr alphabets respectifs Σ et Σ0. Unere´ductionparam´etrique(FPT) de (Q, κ) vers (Q0, κ0) est une fonction :R: Σ0)telle que 1Pour toutxΣ, nous avons (xQR(x)Q0)
r´et(3ee´e)Rctdusnoiarapte´mee´r
elsexpmetlsed´tinisEonReppateirar´msnaptcoi´eduRselpmexexueD.eihrcra´ehiW-Laesquxist3Ileitexplom
On notera(Q, κ)6fpt(Q0, κ0)
De´nition:Re´ductionparame´trique Soient (Q, κ) et (Q0, κ0spmeamarroxp`eblelrusrte´sse´eu)d alphabets respectifs Σ et Σ0. Unere´ductionparam´etrique(FPT) de (Q, κ) vers (Q0, κ0) est une fonction :R: Σ0)telle que 1Pour toutxΣ, nous avons (xQR(x)Q0) 2Rest calculable par un algorithmeFPTap(rtpoaprr`aκ) de complexit´ef(κ(x)).|x|O(1)
´elctesee´cedsessaonspucti´etraramrte´mae´´Rde(e)3´tixrapeoC)MelpmS-NRRMLIPAhe(CULhCirtspo))x(κ(g6))x(R(0κ,ΣtxourtouepquleelNtNel:glubacalctionfonceune
e´apxetimolpMMC)-LIRCNRSAUL(phePotsirhCppaRseel´etditnnsioslpsexEmetqei´eruaLrs´WmaRh)-e´´ieree3r(aicohnised.uDcetumx´eextepmaprlaectesee´redsesdsea´lRxtiiluecmsppcoonam
D´enition:R´eductionparame´trique Soient (Q, κ) et (Q0, κ0de)emesparauxprobl`uslrse´mte´rse alphabets respectifs Σ et Σ0. Unereductionparam´etrique(FPT) de (Q, κ) vers (Q0, κ0) est une ´ fonction :R: Σ0)telle que 1Pour toutxΣ, nous avons (xQR(x)Q0) 2Rest calculable par un algorithmeFPTorppraarat`p(κ) de complexite´f(κ(x)).|x|O(1) 3Il existe une fonction calculableg:NNtelle que pour toutxΣ,κ0(R(x))6g(κ(x)) On notera(Q, κ)6fpt(Q0, κ0)
aretrt´´e