”des outils efficaces pour la resolution exacte de problemes difficiles”

De
Publié par

COMPLEXITE PARAMETREE ”des outils efficaces pour la resolution exacte de problemes difficiles” Christophe Paul Journee scientifique du LIRMM 15 juin 2010

  • histoire de la complexite

  • journee scientifique du lirmm

  • outils efficaces pour la resolution exacte de problemes difficiles

  • theorie de la np-completude

  • problemes np


Publié le : mardi 1 juin 2010
Lecture(s) : 39
Source : lirmm.fr
Nombre de pages : 39
Voir plus Voir moins
”des
´ ´ ´ COMPLEXITE PARAMETREE
outilsecacespourlare´solutionexacte probl`emesdiciles
Christophe Paul
Journ´eescientiqueduLIRMM 15 juin 2010
de
Ide´eadmise:lesprobl`esNP-completssonttous´equivalents! em
I´hT)1:97k1(ooeCedemr`eosatestnp-complet (2-satP)
I12)lptedsKera(p9127probl`emesNP-com
peudhistoiredelacomplexit´e
Th´eoriedelaNP-Comple´tude
ngue3.loelafurldel(Oroum)l
Un
,180pmeloCer´tsenontididenetacnof´tixsederiables2brendevaer1sn.moapar`mteou)p9n,4(1sOleibssopsnoitatcean24m)O(1,useseclaerdmonbmta.23rs-
delaeurlongu)3.l2,m4Os1(uaesedlcembrom.n2
Id´eeadmise:lesprobl`emesNP-completssonttouse´quivalents!
I1(kooCedeme`roe´Th:1)97satestnp-complet (2-satP)
IpraK791(elpmedst2)2mesNP-co1probl`e
Unpeudhistoiredelacomplexit´e
Th´eoriedelaNP-Comple´tude
1.nombrende variables
1.nombrende variables
2naffectations possibles O(1,49n) pour 3-sat
Complexite desatfnnoerapse`masertioctednd´eintre ´
0,1()l8mrofOelu
Unpeudhistoiredelacomplexite´
The´oriedelaNP-Compl´etude
I791(:)1Th´eor`emedeCooksatestnp-complet (2-satP)
Iorlb2p1Ns-Pe`emletscomprp(1deKa)279
Id´eadmise:lesprobl`emesNP-completssonttouse´quivalents! e
Complexit´edesatestr`eamarspntdeie´ernotcoidnenf
1.nombrende variables
1.nombrende variables
2.nombremde clauses
2naffectations possibles O(1,49n) pour 3-sat
O(1,24m)
3.longueurledlaformuleO(1,08l)
Unpeudhistoiredelacomplexit´e
The´oriedelaNP-Compl´etude
Ie´hTedeme`ro97(1okCo:1)satestnp-complet (2-satP)
I-PNspmocstelaKed(1rp2)9721probl`eme
Id´eadmise:lesprobl`emesNP-completssonttous´equivalents! e
Complexite´desatesmararte`ere´pstnndioiednfecton
1.nombrende variables
1.nombrende variables
2.nombremde clauses
3.longueurlde la formule
2naffectations possibles O(1,49n) pour 3-sat
O(1,24m)
O(1,08l)
Vertex
Cover
k-Vertex
v.s.
Cover
Independent
(n
Set
k)-Independent
Set
O2(k.(m+n))O2((nk).(m+n))
Vertex
Cover
k-Vertex
v.s.
Cover
Independent
(n
Set
k)-Independent
Set
O(2k.(m+n))O2((nk).(m+n))
Vertex
Coverv.s.
k-Vertex
O(2k.(m
Cover
+n))
Independent
(n
Set
k)-Independent
Set
O2((nk).(m+n))
Vertex Coverv.s.
k-Vertex Cover
O(2k.(m+n))
Independent Set
(nk)-Independent
O(2(nk).(m+n))
Set
nentexpoedutiellalrcelednaecioss`eamarnpecp´estracedspmeua`,luclbinatoire,sembleerlxelpsooicnmoui,qtrespoesabnsi-t-´niltiveelbaIeLrGhodn.MulamJ.Fe...nn´ecedodniertseredtseeltaenamndfoeed´itruoetniegioner´eesignideladonnnilnatsllerrusetrnstuucrmfoioatblrome`equiupearedeeiem...iN.Rr
Constat:De peuventeˆtre pratiques
nombreux r´esolusde
probl`emesdiciles(np-complet) maniereecacesurdesdonne´es `
emtnneof´tseueellataillenctiondeMImpcoxileureslaerI
qciauueobpreml`apnu`marertee´pstempsdecalcul,`aeepxnoneitleeludaceledblncsaisrotseiuq,easnopseriline-t-tabl´evitaiobmnimelbers,isolocnolerdpxestreinreeealdestnoademtnLdie´feIeirmdeie.NR..e.
Constat:moneDmesdbl`exprobreuelsiic(np-complet) ntˆtrer´esolusdemanie`reecacesurdesdonn´ees peuve e pratiques
I
I
Mesurerlacomplexit´eseulementenfonctiondelatailledela donn´eesignieignorertouteinformationstructurellesur l’instance d ´ ” onnee. . .
J. Flum and M. Grohe
re
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.