Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

De
39 pages
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


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin