Cours d’Algorithmique

Cours d'algorithmique 11 / IntranetCours d'algorithmique 11 / Intranet 119 janvier 20069 janvier 2006

Cours d’AlgorithmiqueCours d’Algorithmique

N PN P--complétude.complétude.

9 janvier 20069 janvier 2006 Cours d'algorithmique 11 / IntranetCours d'algorithmique 11 / Intranet 22

• Trier et chercher, recherche textuelleTrier et chercher, recherche textuelle• Listes et arbresListes et arbres• Le back-trackLe back-track• Arbres équilibrésArbres équilibrés• Récursivité et induction sur la structureRécursivité et induction sur la structure• Divide and conquer, algorithmes gloutonsDivide and conquer, algorithmes gloutons• Minimax, alpha-betaMinimax, alpha-beta• DérécursionDérécursion• NP-complétudeNP-complétude• Logique de HoareLogique de Hoare• Programmation dynamiqueProgrammation dynamique• Complexité et calculabilitéComplexité et calculabilité

Les grandes lignes du coursLes grandes lignes du cours


Le problèmeLe problème----------------------------------------------------------------------------------------------------------------------------------

• Nous avons vu le « action selection problem » :Nous avons vu le « action selection problem » :

– en back-track avec une complexité exponentielle,en back-track avec une complexité exponentielle,

– en programmation dynamique avec une complexité quadratique,en programmation dynamique avec une complexité quadratique,

– comme algorithme glouton avec une complexité linéaire.comme algorithme glouton avec une complexité linéaire.

• Nous avons vu la « satisfaction d’une formule logique » :Nous avons vu la « satisfaction d’une formule logique » :

– en back-track avec une complexité exponentielle,en back-track avec une complexité exponentielle, (équivalant au parcours de la table de vérité),(équivalant au parcours de la table de vérité),

– et puis … ?et puis … ?

– Rien ! ! !Rien ! ! !



• La question :La question :

• Y aurait-il par hasard des problèmes dont la complexité intrinsèque Y aurait-il par hasard des problèmes dont la complexité intrinsèque est exponentielle ?est exponentielle ?

• Pour un tel problème, tout algorithme pour le résoudre serait Pour un tel problème, tout algorithme pour le résoudre serait exponentiel en temps !exponentiel en temps !

• La réponse :La réponse :

• Probablement OUI !Probablement OUI !

• Malheureusement ! ! !Malheureusement ! ! !

• On ne sait rien de définitif ! ! !On ne sait rien de définitif ! ! !

P = N PP = N P

ou bienou bien

P = N PP = N P

//



• La question de la « La question de la « N P N P – complétude » :– complétude » :

P = N PP = N P

ou bienou bien

P = N PP = N P

//



• On connaît des centaines et des centaines de On connaît des centaines et des centaines de problèmes « problèmes « N P N P – complets » :– complets » :

– Si Si P P == N P N P (probable) :(probable) :

Tous ont une complexité exponentielle !Tous ont une complexité exponentielle !

– Si Si P P = = N P N P (peu probable) :(peu probable) :

Tous ont une complexité polynômiale !Tous ont une complexité polynômiale !

• C’est sans doute le problème informatique non résolu C’est sans doute le problème informatique non résolu le plus important ! ! !le plus important ! ! !

//



Les problèmes « Les problèmes « N P N P – complets » sont aussi appelés :– complets » sont aussi appelés :

INTRACTABLES !!!INTRACTABLES !!!

Parce que : Parce que : 2^10 = 1024 2^10 = 1024 2^20 = 10485762^20 = 1048576 2^30 = 10737418242^30 = 1073741824 2^50 = 11258999068426242^50 = 1125899906842624



• Un problème « Un problème « N P N P – complet » est,– complet » est,

– de manière informelle,de manière informelle,– mais correspondant à la pratique : mais correspondant à la pratique :

• un problème de décision ( OUI – NON )un problème de décision ( OUI – NON )

• qui se résout (pour l’heure) par back-trackqui se résout (pour l’heure) par back-track (ou équivalent en complexité).(ou équivalent en complexité).



• Un problème « Un problème « N P N P – complet » est,– complet » est,

– de manière informelle,de manière informelle,– mais correspondant à la pratique : mais correspondant à la pratique :

• un problème de décision ( OUI – NON )un problème de décision ( OUI – NON )

• qui se résout (pour l’heure) par back-trackqui se résout (pour l’heure) par back-track (ou équivalent en complexité).(ou équivalent en complexité).

Plus difficile :Plus difficile :

difficiledifficile

d’optimisation ( le meilleur, … )d’optimisation ( le meilleur, … )

completcomplet


Des exemplesDes exemples----------------------------------------------------------------------------------------------------------------------------------

• « SAT » est « « SAT » est « N P N P –complet » :–complet » :

• « n » variables logiques,« n » variables logiques,

• une formule logique construite sur ces variables à une formule logique construite sur ces variables à l’aide de l’aide de et, ou et, ou et et not.not.

• La question ( toute simple ) :La question ( toute simple ) :

Est-il possible de donner des valeursEst-il possible de donner des valeurs aux variables logiques de manière àaux variables logiques de manière à

rendre vraie la formule ?rendre vraie la formule ?

• La solution :La solution :

Essayez tout ! Essayez tout !



• Attention :Attention :

• Parfois c’est simple ! ! !Parfois c’est simple ! ! !

• a b . . . za b . . . z

a v ( . . . )a v ( . . . )

• Mais, dans le cas général (c’est-à-dire le plus Mais, dans le cas général (c’est-à-dire le plus

souvent),souvent),

c’est difficile ! ! !c’est difficile ! ! !

vvvv vv



• Le « Voyageur de Commerce », en anglais « Traveling Le « Voyageur de Commerce », en anglais « Traveling Salesman Problem » ( TSP ), est « Salesman Problem » ( TSP ), est « N P N P –difficile » :–difficile » :

• « n » villes,« n » villes,

• un réseau routier entre ces villes avec les distances,un réseau routier entre ces villes avec les distances,

• La question :La question :

Quel est le coût du circuit (point de départQuel est le coût du circuit (point de départ = point d’arrivée) le moins cher qui visite= point d’arrivée) le moins cher qui visite

chaque ville une et une seule fois ?chaque ville une et une seule fois ?

• La solution :La solution :

Essayez tout ! Essayez tout !


N P N P – complétude – complétude ----------------------------------------------------------------------------------------------------------------------------------

• La classe de problèmes « La classe de problèmes « P »P » ! !

• Ce sont les problèmes qui acceptent un algorithme : Ce sont les problèmes qui acceptent un algorithme :

– polynômial,polynômial,

– déterministe,déterministe,

– qui résout toutes les instances.qui résout toutes les instances.

La complexité est un polynômeLa complexité est un polynômeen termes de la taille du problème.en termes de la taille du problème.

Il n’y a aucun élément de chance ouIl n’y a aucun élément de chance oud’indication venant de l’extérieur.d’indication venant de l’extérieur.

Aucune instanceAucune instancen’est trop difficile.n’est trop difficile.



• La classe de problèmes « La classe de problèmes « N N P »P » ! !

• Ce sont les problèmes qui acceptent un algorithme : Ce sont les problèmes qui acceptent un algorithme :

– polynômial,polynômial,

– nonnon--déterministe,déterministe,

– qui résout toutes les instances.qui résout toutes les instances.

Il peut y a avoir des élémentsIl peut y a avoir des élémentsde chance ou desde chance ou des

indications venant de l’extérieur.indications venant de l’extérieur.



• La classe de problèmes « La classe de problèmes « NN P »P » ! !

• Il est clair que : Il est clair que :

P N PP N P

• Mais ?Mais ?

P = N P P = N P ou ou P = N P P = N PUU

//




ICI !ICI !




ICI !ICI !




ICI !ICI !




ICI !ICI !



• Nous remplaçons une exploration à l’aide du back-track Nous remplaçons une exploration à l’aide du back-track

– par un appel à l’oracle.par un appel à l’oracle.

• L’oracle répond au bout de . . . ?L’oracle répond au bout de . . . ?

– La complexité de l’oracle est bien-sûr en O ( 1 ) .La complexité de l’oracle est bien-sûr en O ( 1 ) .

• Je sais réaliser un oracle en temps exponentiel !Je sais réaliser un oracle en temps exponentiel !

– Il suffit de faire un back-track en cachette ! ! !Il suffit de faire un back-track en cachette ! ! !



• Une autre façon de voir les choses :Une autre façon de voir les choses :

• SiSi

P = N PP = N P

• alorsalors

l’oracle, c’est-à-dire le choixl’oracle, c’est-à-dire le choix

peut toujours être calculé en temps polynômial !peut toujours être calculé en temps polynômial !



• Autre formulation de la classe de Autre formulation de la classe de problèmes « problèmes « N N P »P » ! !

• Ce sont les problèmes qui : Ce sont les problèmes qui :

– acceptent, pour chaque instance, un nombre acceptent, pour chaque instance, un nombre borné de candidats à être la solution,borné de candidats à être la solution,

– pour lesquels, la vérification qu’un candidat pour lesquels, la vérification qu’un candidat quelconque est solution appartient à « quelconque est solution appartient à « P P ». ».



• Théorème :Théorème :

P N PP N P

UU

N PN P

PP

P = N PP = N P c’est-à-dire c’est-à-dire N P \ P = N P \ P = oo||?? ??

? ? ? ? ?? ? ? ? ?



• Définissons la classe « Définissons la classe « N P C N P C », c’est-à-dire les », c’est-à-dire les problèmes « Nproblèmes « N--PP--complets » :complets » :

N PN P

PP

N P CN P C

Ce seront les problèmes les plus difficiles de « Ce seront les problèmes les plus difficiles de « N P » !N P » !

L’idée : Si eux sont dans « L’idée : Si eux sont dans « PP », alors », alors « « P = N P P = N P »» ! ! ! ! ! !

Facile.Facile.

Difficile.Difficile.



• Il nous faut une notion de traduction !Il nous faut une notion de traduction !

– Soit un problème P : D Soit un problème P : D --> BOOL> BOOL

– Soit un problème P : D Soit un problème P : D --> BOOL> BOOL

• P se réduit en P , noté P <= P , si et seulement si :P se réduit en P , noté P <= P , si et seulement si :

– il existe f : D il existe f : D --> D> D

– telle que pour tout x telle que pour tout x D : D :

P ( x ) = P ( f ( x ) )P ( x ) = P ( f ( x ) )

1111

2222

11 1122 22

11 22

11

11 22



• L’idée derrière la traduction :L’idée derrière la traduction :

PP11

xx Vrai ou FauxVrai ou FauxCalcul !Calcul !

PP22

f ( x )f ( x )

Traduction !Traduction !

Vrai ou FauxVrai ou FauxCalcul !Calcul !

Le mêmeLe mêmerésultat !résultat !



• Un exemple :Un exemple :

– Les booléens : Vrai Faux Les booléens : Vrai Faux et ou not et ou not

– Les entiers : 1 0 * Les entiers : 1 0 * maxmax ( 1 ( 1 -- _ ) _ )


– F = Vrai si et seulement si f ( F ) = 1F = Vrai si et seulement si f ( F ) = 1

f :f :

BOOLBOOL BOOLBOOL

Vrai Vrai et et ( Faux ( Faux ouou notnot ( Faux ) ) = Vrai ( Faux ) ) = Vrai

1 * ( 0 1 * ( 0 maxmax ( 1 ( 1 -- 0 ) ) = 1 0 ) ) = 1



• Si P <= P et que A résout P :Si P <= P et que A résout P :11 22 22 22

yy P ( y )P ( y )22

AA22

xxff

f ( x )f ( x ) P ( f ( x ) )P ( f ( x ) )22xx P ( x )P ( x )11



• Il nous faut une réduction en temps raisonnable !Il nous faut une réduction en temps raisonnable !

• P se réduit polynômialement en P , noté P <= P , si et P se réduit polynômialement en P , noté P <= P , si et seulement si :seulement si :

– il existe f : D il existe f : D --> D avec f > D avec f PP

– telle que pour tout x telle que pour tout x D : D :

P ( x ) = P ( f ( x ) )P ( x ) = P ( f ( x ) )

• <= est un pré-ordre :<= est un pré-ordre :

– réflexitivité, transitivité, OK. réflexitivité, transitivité, OK.

– Non anti-symétrique : P <= P et P <= P ,Non anti-symétrique : P <= P et P <= P ,

mais P = Pmais P = P

11 1122 22

11 22

11

11 22

PP

PP

11 22PP 22 11PP

2211//




• Soient P et P avec P <= P :Soient P et P avec P <= P :

– Si P Si P PP alors P alors P PP . .


• Donc, P est au moins aussi difficile que P .Donc, P est au moins aussi difficile que P .

• Preuve (première condition) :Preuve (première condition) :

– Si P Si P PP alors il existe A pour le résoudre de manière alors il existe A pour le résoudre de manière déterministe et en tempsdéterministe et en temps polynômial ! polynômial !

– Il suffit de composer A avec la fonction de traduction f .Il suffit de composer A avec la fonction de traduction f .

11 1122 22

22

22//11

PP

1122

11

//

22 22

22




• Soient P et P avec P <= P :Soient P et P avec P <= P :



• Donc, P est au moins aussi difficile que P .Donc, P est au moins aussi difficile que P .

• Preuve (seconde condition) :Preuve (seconde condition) :

– Par absurde : Il n’est pas possible que P Par absurde : Il n’est pas possible que P PP et que P et que P PP . .

– Il existerait A dans Il existerait A dans P P pour résoudre P et il suffirait depour résoudre P et il suffirait de

composer A avec la fonction de traduction f . . .composer A avec la fonction de traduction f . . .

11 1122 22

22

22//11

PP

1122

11

//

22 22

22

22//11



• Définition :Définition :

• La classe « La classe « N P CN P C » est la classe des problèmes P tels que : » est la classe des problèmes P tels que :

– P P N PN P . .

– Pour tout Q Pour tout Q N PN P on a : Q <= P . on a : Q <= P .

• Tout le monde se réduit vers P .Tout le monde se réduit vers P .

• P est donc le plus difficile ! ! !P est donc le plus difficile ! ! !

• Si P , P’ Si P , P’ N P CN P C , alors il sont « ex aequo » en difficulté : , alors il sont « ex aequo » en difficulté :

P <= P’ et P’ <= P .P <= P’ et P’ <= P .

PP

PP PP



• Schématiquement :Schématiquement :

• Globalement,Globalement,

– il suffit de savoir résoudre un seul problème, P par exemple,il suffit de savoir résoudre un seul problème, P par exemple,

– et de traduire tous les autres vers P .et de traduire tous les autres vers P .

N PN PN P CN P C PP P’P’<=<=

PP

>=>=PP

<=

<= PP

AA

>=

>=

PPBB

<=

<= PP

CC



• Et si « Et si « N P CN P C » était vide ? ? ? » était vide ? ? ?

– C’est-à-dire, un tel problème universel n’existe pas ! ! !C’est-à-dire, un tel problème universel n’existe pas ! ! !

• Théorème (Cook, 1971) :Théorème (Cook, 1971) :

– SAT SAT N P CN P C . .

• Il n’y a pas plus difficile (dans Il n’y a pas plus difficile (dans N P N P C) que la logique.C) que la logique.

• Principe de la preuve :Principe de la preuve :

– Tout problème dans « Tout problème dans « N PN P » peut être traduit en une formule logique. » peut être traduit en une formule logique.

– Analogie : Tout texte peut être traduit en une formule alphabétique.Analogie : Tout texte peut être traduit en une formule alphabétique.



• Conséquences :Conséquences :

• S’il existe un seul problème PS’il existe un seul problème P N P CN P C

– pour lequel on trouve un algorithme en temps polynômial pour lequel on trouve un algorithme en temps polynômial et déterministe,et déterministe,

– alors alors P = N P P = N P !!

• S’il existe un seul problème PS’il existe un seul problème P N P CN P C

– pour lequel on prouve qu’un algorithme en temps pour lequel on prouve qu’un algorithme en temps polynômial et déterministe ne peut pas exister,polynômial et déterministe ne peut pas exister,

– alors alors P = N P P = N P !!

//



• Concrètement :Concrètement :

• Vous avez un problème qui vous résiste !Vous avez un problème qui vous résiste !

• Essayez de savoir s’il est Essayez de savoir s’il est NN--PP--complet !complet !

– le Garey and Johnson,le Garey and Johnson,

– ou Internet,ou Internet,

– ou prouvez-le vous-même.ou prouvez-le vous-même.

• Comment faire ?Comment faire ?

– Prouvez que votre problème P est dans Prouvez que votre problème P est dans N P N P etet

– prenez un problème A de prenez un problème A de N P C N P C et montrez que A <= Pet montrez que A <= P

PP



• Concrètement :Concrètement :

• Si, par malheur, il l’est . . .Si, par malheur, il l’est . . .

– Est-ce que j’ai vraiment besoin de ce résultat ?Est-ce que j’ai vraiment besoin de ce résultat ?

– Si oui . . .Si oui . . .

• Est-ce que mon instance est par chance suffisamment petite ?Est-ce que mon instance est par chance suffisamment petite ?

– Est-ce que je peux me contenter d’un résultat approché ?Est-ce que je peux me contenter d’un résultat approché ?

• L’idée derrière le résultat approché :L’idée derrière le résultat approché :

• Il est peut-être pas loin d’être optimal ( par exemple à 5% deIl est peut-être pas loin d’être optimal ( par exemple à 5% de

l’optimum ), mais il est dans « l’optimum ), mais il est dans « PP » ( par exemple en n^2 ) . » ( par exemple en n^2 ) .



• Quelques problèmes de « Quelques problèmes de « N P CN P C » ! » !

• SATSAT

– « n » variables logiques et une formule « F » construite sur ces variables à « n » variables logiques et une formule « F » construite sur ces variables à l’aide de l’aide de et et , , ou ou ou ou not not ..

– La question : F peut-elle prendre la valeur Vrai pour un choix adéquat des La question : F peut-elle prendre la valeur Vrai pour un choix adéquat des valeurs des variables ?valeurs des variables ?

• 3-SAT3-SAT

– « n » variables logiques et une formule « F » en forme normale conjonctive « n » variables logiques et une formule « F » en forme normale conjonctive avec 3 littéraux par disjonction.avec 3 littéraux par disjonction.

Exemple : ( x v x v Exemple : ( x v x v x ) ( x v x ) ( x v x v x v x ) x )

– Même question !Même question !

• 2-SAT 2-SAT PP 11 33 55 33 22 44

vv




• Circuit-SATCircuit-SAT

– « n » variables logiques et un circuit logique construit à partir des « n » variables logiques et un circuit logique construit à partir des circuits de base circuits de base et et , , ou ou ou ou not not ..

– La question : Le circuit peut-il rendre la valeur Vrai pour un choix La question : Le circuit peut-il rendre la valeur Vrai pour un choix adéquat des valeurs des variables ?adéquat des valeurs des variables ?

• Exemple de réduction :Exemple de réduction :

– Admettons que 3-SAT soit connu pour appartenir à « Admettons que 3-SAT soit connu pour appartenir à « N P CN P C ». ».

– Démontrons que Circuit-SAT appartient aussi à « Démontrons que Circuit-SAT appartient aussi à « N P CN P C » ! » !



• La réduction :La réduction :

– Variable 3-SAT Variable 3-SAT --> variable Circuit-SAT.> variable Circuit-SAT.

– x x --> > xx

– ( a v b v c ) ( a v b v c ) --> > aa

bb cc

– ( a b . . . z ) ( a b . . . z ) --> > aa bb . . . . . . . . . . . .

zz

vvvv vv

. . .. . . La réductionLa réductionest dans est dans PP ! !




• Subset-SumSubset-Sum

– Un ensemble E de « n » entiers naturels et une constante sUn ensemble E de « n » entiers naturels et une constante s ..

– La question : Existe-il un sous-ensemble I de E tel que la La question : Existe-il un sous-ensemble I de E tel que la somme des éléments de I soit égale à s ?somme des éléments de I soit égale à s ?

• Set-PartitionSet-Partition

– Un ensemble E de « n » entiers naturels.Un ensemble E de « n » entiers naturels.

– La question : Existe-il un sous-ensemble I de E tel que la La question : Existe-il un sous-ensemble I de E tel que la somme des éléments de I soit égale à la somme des éléments somme des éléments de I soit égale à la somme des éléments de l’ensemble complémentaire ?de l’ensemble complémentaire ?




• Programmation entièreProgrammation entière

– Une matrice entière M et un vecteur entier b .Une matrice entière M et un vecteur entier b .

– La question : Existe-il un vecteur x tel que M * x <= b ?La question : Existe-il un vecteur x tel que M * x <= b ?

• Programmation entière en 0 Programmation entière en 0 -- 1 1

– Une matrice entière M et un vecteur entier b .Une matrice entière M et un vecteur entier b .

– La question : Existe-il un vecteur x avec des valeurs 0 ou 1 tel La question : Existe-il un vecteur x avec des valeurs 0 ou 1 tel que M * x <= b ?que M * x <= b ?

• Et des milliers d’autres . . . Et des milliers d’autres . . .

Documents

Cours d’Algorithmique