Théorie de la Complexité

H. Hasni
Ecole Nationale des Sciences de l’Informatique
Université de Manouba
2010 Campus Universitaire – Manouba

E-mail : [email protected]

1
 Plan
 Qu’est-ce que la complexité ?
 Modèles Abstraits de Calcul
 Machines de Turing
 Problèmes de Décision
 Classes de Complexité
 Réductions de Problèmes
 NP-Complétude
 Exemples de Problèmes NP-Complets
 Exemples de Réduction
 P = NP ?
 Que faire devant un Problème NP?
 Classe de Complexité co-NP

2
Introduction
 La théorie de la complexité s’intéresse à l’étude formelle de la
difficulté des problèmes en informatique.

 Gödel (1932) : premier théorème d’incomplétude (toute

théorie contient des énoncés non démontrables)

 Turing, Church (1936) : réponse négative au problème de la

décision (cf. machine de Turing et le problème de l’arrêt)

 Edmonds (1965) : Distinction entre les problèmes P et NP

Cook (1971)- Levin (1973) : NP – Complétude ( Problème SAT)

 Karp (1972) : Liste de 21 nouveaux problèmes NP-Complet.

 Aujourd’hui la conjecture P = NP ? fait partie des 7 problèmes du millénaire.

3
Qu’est – ce que la complexité ?(1)
 Question centrale de l’Informatique
théorique :
 Limites des Ordinateurs
 Limites fondamentales indépendantes de la
technologie
 Peut-on identifier les problèmes de
calcul qui sont hors de portée ?

4
 Qu’est – ce que la complexité ?(2)

Taille n Opérations
élémentaires

Entrées Algorithme Résultat

Temps Ressources Espace

5
Qu’est – ce que la complexité ?(3)
 Complexité:
 En pratique, un algorithme consomme une
quantité raisonnable de ressources de calcul :
 Nombre d’opérations,
 Temps de calcul
 Quantités de mémoire
 Complexité : quantité minimale de ressources
nécessaire à sa résolution.

6
Qu’est – ce que la complexité ?(4)
 Les notions de temps de traitement, d’espace sont
dépendant de la machine physique utilisée.
 Besoin d’une mesure absolue indépendante de
toute implémentation.
 Facteurs de temps de calcul :
 Taille de l’entrée
 Ordinateur utilisé
 Langage de programmation utilisé

7
Modèles Abstraits de Calcul(1)
 Théorie robuste indépendante de la machine
 Nécessité de s’entendre sur des modèles de calcul
 Définition formelle de la notion d’algorithme
(Modèles abstraits de Calcul ,1936)
 Machine de Turing
 Machine de Post
 Fonctions récursives de Kleene
 -calcul de Church
 Machine RAM
Tous ces modèles sont équivalents

Remarque : Toutes les architectures de machines réelles sont équivalentes à la

machine de Turing ( elles sont plus « puissantes » mais pas plus
« expressives » )

8
 Modèles Abstraits de Calcul(2)
 Théorie de la Complexité :

 Classification des problèmes suivant le temps et

l’espace nécessaire à la résolution de l’instance la plus
« dure » du problème sur un modèle théorique :
machine de Turing.

9
Machines de Turing (1)
Alan Matheson Turing
(1912 – 1954)

 Inventeur de la Machine
de Turing ( 1936)

 Machine ENIGMA

10
Machines de Turing (2)
 Machines de Turing
 Définition : Une machine de TURING déterministe (MTD) est donnée
par M = (Q, ,  , , q0 ,F) , où :
 Q est un ensemble fini d’état,
  est un alphabet
    ( alphabet d’entrée),
 F  Q est l’ensemble des états accepteurs
  : D  Q x   Q x  x {L,R}, fonction de transition
 q0 : état initial
- Un symbole spécial B appelé caractère blanc
- L et R représentent les 2 directions de déplacement de la tête de lecture
- Une configuration est un élément de Q x * x IN (* : ensemble des mots)

11
Machine de Turing (3)
Une machine de Turing peut
 S’arrêter :

 Un état accepteur
 Une configuration où  n’est pas définie
 On ne peut pas déplacer la tête de lecture
comme indiqué
 Ne jamais s’arrêter

12
Machine de Turing (4)
 Machine de Turing Non Déterministe (MTND) :

 Variante purement théorique jusqu’à l’arrivée des

ordinateurs quantiques

 Tout choix est fait au hasard :

 Mais elles trouvent toujours le bon chemin!!!

 On peut aussi considérer qu’elles se dupliquent

à chaque décision, chacune partant sur une des

« branches » d’exécution

13
Machine de Turing (5)
 Machine de Turing Non Déterministe (MTND) :
 Définition : Une machine de TURING non déterministe
(MTND) est donnée par M = (Q, ,  , , q0 ,F) , où :

 Q est un ensemble fini d’état,

  est un alphabet
    ( alphabet d’entrée),
 F  Q est l’ensemble des états accepteurs

 : D  Q x   P (Q x  x {L,R}), fonction de transition
 q0 : état initial

14
Décidabilité – Calculabilité (1)
 Un langage est accepté par une machine de Turing s’il
existe une machine de Turing qui accepte dans un temps
fini tous les mots du langage.

 Un langage est décidé par une machine de Turing s’il

existe une machine de Turing qui accepte le langage et qui
s’arrête toujours.

15
 Décidabilité – Calculabilité (2)
 Un langage est dit récursif s’il est décidé par une machine
de Turing.

 Un algorithme est un ensemble fini d’instructions décrivant

le déroulement des opérations pour résoudre un problème et
ce déroulement doit toujours se terminer dans un temps fini

 Un problème est décidable s’il existe une machine de

Turing s’arrêtant toujours autrement il est dit indécidable

16
 Décidabilité – Calculabilité (3)
David Hilbert
(1862 –1943)

 Liste des 23 problèmes de

Hilbert (1900)
 Problème numéro 10 :
« Existe-t-il un procédé mécanique
permettant de dire, après un
nombre fini d'étapes, si une
équation diophantienne donnée
possède des solutions entières?».
est indécidable (Théorème de
Matiyasevich (1970))
17
Décidabilité – Calculabilité (4)
 On appelle équation diophantienne une équation du genre
P(x, y, z, ...) = 0, où P est un polynôme à coefficients
entiers. Résoudre une telle équation, c'est chercher les
solutions sous forme d'entiers.
L’équation x2 + y2 – 1 = 0 est une équation diophantienne
qui admet pour solutions: x = 1, y = 0 et x = 0, y = 1
 L'équation x2 – 991 y2 – 1 = 0 est également
diophantienne mais a des solutions beaucoup plus
difficiles à trouver la plus petite est :
 x = 379 516 400 906 811 930 638 014 896 080 et
 y = 12 055 735 790 331 359 447 442 538 767

18
Décidabilité – Calculabilité (5)
 Problème de l’arrêt (proposé par A. Turing 1936) :
 Soit un programme informatique et une entrée à ce
programme, déterminez si ce programme va terminer
sur cette entrée ou continuer à s’exécuter indéfiniment
 Théorème : Le problème de l’arrêt est indécidable
 Preuve ( par contradiction) :
 Soit un algorithme A qui résout le problème de

l’arrêt. Dans ce cas, pour tout programme P et une

entrée E, nous avons:
A(P,E) = 1 si P termine sur E
0 si P ne termine pas sur E

19
 Décidabilité – Calculabilité (6)
 Preuve (suite)
 Tout programme P peut être utilisé comme entrée à lui même
 Utilisons l’algorithme A sur (P,P) pour construire un programme
Q ayant la propriété suivante :

 Q(P) termine lorsque A(P,P) = 0 ( lorsque P ne termine pas sur P)

 Q(P) ne termine pas lorsque A(P,P) = 1 (lorsque P termine sur P)

 Si nous utilisons Q comme entrée sur lui-même nous obtenons:

 Q(Q) termine lorsque A(Q,Q) = 0 (lorsque Q ne termine pas)
 Q(Q) ne termine pas lorsque A(Q,Q) = 1 (lorsque Q termine
sur Q
 Un tel programme Q ne peut exister. Il en va donc de même
pour l’algorithme A. CQFD

20
 Décidabilité – Calculabilité (7)
Alonzo Church
(1903 – 1995)

 Résultat sur la calculabilité

 Développement du lambda-calcul

 1936 : Existence d ’un problème

indécidable

 Thèse de Church

21
 Décidabilité – Calculabilité (8)
Kurt Godël
(1906 – 1978)

 Théorème d’Incomplétude
 Complétude : Une théorie mathématique pour
laquelle tout énoncé est décidable est dite complète,
sinon elle est dite incomplète

 Théorème de Godel(1932) : Dans n'importe

quelle théorie récursivement axiomatisable,
cohérente et capable de « formaliser
l'arithmétique », on peut construire un énoncé
arithmétique qui ne peut être ni prouvé ni réfuté
dans cette théorie

22
Décidabilité – Calculabilité

23
 Décidabilité – Calculabilité (10)

Thèse de Church – Turing :

Un langage est calculable si ce langage

est récursif i.e. décidé par une machine de
Turing

24
Complexité Algorithmique
 Complexité temporelle pire cas d’une machine de Turing :
nombre maximal de déplacements de la tête de
lecture/écriture pour résoudre une instance de taille
maximale n
 La taille de l’instance est la longueur de la séquence
binaire codant cette instance comme une entrée de la
machine de Turing
 Complexité spatiale pire cas : longueur de bande
nécessaire à la machine pour résoudre une instance de
taille n

25
Problèmes de Décision (1)
 Un problème désigne la description générale d’une
question.Par exemple : Trouver un facteur non trivial d’un
entier
 Résoudre un problème : essayer de décrire un algorithme
(par exemple à formaliser par une machine de Turing)
 Un problème de décision (d’existence ou de
reconnaissance) consiste à chercher dans un ensemble fini
s’il existe un élément vérifiant une certaine propriété.
 Un problème de décision peut être formulé par un énoncé
et une réponse Oui – Non

26
Problèmes de Décision (2)
 La forme générale d’un problème de décision :
 Une description de l’instance du problème
 L’expression d’une question Oui/non portant sur cette
instance
 Exemples :
 Voyageur de Commerce ( TSP) :
 Données : un graphe complet d’ordre n valué par des entiers
positifs et un entier k
 Question : Existe –t- il dans le graphe un cycle hamiltonien de
longueur  k ?

27
Problèmes de Décision (3)
 Exemples :
 Clique :
 Données : un graphe et un entier positif k
 Question : G contient –t-il un sous-graphe complet à k
sommets ?
 Recouvrement ( Set Cover ):
 Données : Un ensemble X et une famille f de sous-ensembles
de X
 Question : Existe –t-il une sous – famille f’ de f telle que tout
élément de X appartient exactement à un élément de f ?

28
Problèmes de Décision (4)
 Notations : soit D l’ensemble des instances possibles
d’un problème de décision 

 Y : sous-ensemble des instances pour lesquelles la

réponse est Oui (Yes)

 N : sous-ensemble des instances pour lesquelles la

réponse est Non (No)

29
Problèmes de Décision (5)
 Lien entre Problème de Décision et Langages:

 Fonction de codage C : traduction d’une instance en un

mot sur un alphabet.

 Une machine de Turing M résout le problème décision

 , sous le codage C, si M s’arrête sur toute entrée x et si
l’ensemble des mots acceptés par M est égal à
l’ensemble L[, c]de mots qui résultent du codage
d’instance de Y .

30
 Problème de Décision (6)
Problème de décision
& langage accepté par une machine de Turing
Tête de
Controleur lecture /
d'états finis écriture

  l ’ensemble des symboles pouvant être écrit par l ’utilisateur sur le ruban
 * l ’ensemble des mots du langage sur l ’alphabet
 LM = { x  * : M accepte x }
 Résoudre le problème revient à savoir si x  LM
31
 Problème de Décision (7)
 Codage des entiers positifs :
 Codage binaire efficace : i est codé par la
séquence
n k
i   ik .2 avec ik 0,1
k 0
La longueur l1(i) des codes de i est de l’ordre de Log2(i)
 Codage binaire inefficace : i est codé par une
séquence de 1 de longueur i

La longueur l2(i) des codes de i est de l’ordre de 2 l1(i)

32
 Problème de Décision (8)
 Codage d’un graphe
Encodage Chaîne

 Liste des sommets/liste des arêtes : x[1] x[2] x[3] x[4](x[1] x[2])(x[1] x[3])(x[2] x[3])(x[3] x[4])

Liste des voisins : (x[2] x[3])(x[1] x[3])(x[1] x[2] x[4])(x[3])

Matrice d’adjacence : 0110/1010/1101/0010

33
Classes de Complexité (1)
 Complexité en temps d’une machine de Turing
s’arrêtant toujours :

TM(n) = Max {m /  x * , |x| = n et l’exécution de

M sur x comporte m étapes }

 La classe P est la la classe des langages décidés par

une machine de Turing polynomiale i.e
 un polynôme p(n) tel que :
TM  p(n) pour tout n  0

34
Classes de Complexité (2)
 Le temps de calcul d’une machine de Turing ND
sur un mot w est donné par :
 La longueur de la plus courte exécution acceptant le mot
si celui-ci est accepté.
 La valeur 1 si le mot w n’est pas accepté

 Complexité en temps d’une machine de Turing

non déterministe
TMND(n) = Max {m /  x * , |x| = n et le temps de
calcul de M sur x est m}

35
Classe de Complexité (3)
 La classe NP ( Non déterministe Polynomiale) est
la classe des langages acceptés par une machine
de Turing non déterministe polynomiale

 Solution rapide si l’énumération des cas ne coûte

rien

 Exemple : Circuit hamiltonien (HC)

36
 Classe de Complexité (4)
Exemple : Circuit Hamiltonien

 Un circuit hamiltonien est un

chemin de G passant une et une
seule fois par chacun des sommets
et revenant à son point de départ

 Un graphe biparti d’ordre impair n’a

pas de circuit hamiltonien.

37
Classe de Complexité (5)
 Théorème :
Soit L  NP. Il existe une machine de
Turing déterministe M et un polynôme p(n)
tel que M décide L et est de complexité en
temps bornée par 2p(n)
( Simuler toutes les exécutions de MND)

38
Classe de Complexité (6)
 Preuve :
 Soit une MTND de complexité polynomiale q(n) qui accepte L. Simuler
toutes les exécutions de MTND de longueur inférieure à q(n). Pour un mot
w, la machine doit:

 1. Déterminer la longueur n de w et calcule q(n) . polynôme

 2. Simuler chaque exécution de MTND de longueur q(n) (temps
nécessaire q’(n)).Si r est le nombre maximum de choix possibles de
MTND à chaque étape de son exécution, il y a au plus r q(n) exécutions
de longueur q’(n)
 3. Si une des exécution simulées accepte, M accepte. Sinon M s’arrête
et rejette le mot w

 Complexité bornée par rq(n) x q’(n) et donc par 2 log2(r)(q(n)+q’(n)) qui de la

forme de 2p(n)

39
Classe de Complexité (6)
 Pour Prouver qu’un problème est dans NP :

 Proposer un codage de la solution ( certificat)

 Proposer un algorithme vérifiant la solution au vu des

données et du certificat

 Montrer que cet algorithme a une complexité

polynomiale.

40
Classe de Complexité (7)
 Exemples
 Voyageur de commerce
 Certificat : indication d’un circuit de longueur
inférieur à k
 Clique :
 Certificat : indication de k sommets du graphe
d’entrée constituant une clique
 Recouvrement : indication d’un sous-famille
vérifiant la propriété demandée

41
Classe de Complexité (8)
 Un grand nombre des problèmes de NP est que, on ne
sait pas dire, s’ils sont ou non polynomiaux.
 On ne sait pas produire une solution polynomiale,

 On ne sait pas non plus démontrer que le problème est non

polynomial

 Que faire ?
 Comparer la difficulté du problème NP considéré à celle
d’autre problèmes NP.
 Réduction d’un problème à un autre

42
 Classe de Complexité (9)
 Equivalence entre Problèmes

43
Réduction de Problèmes (1)
 Transformations (Réductions) polynomiales
 Définition : Soient un langage L1 et un langage L2. Une
transformations polynomiale de L1 vers L2 (notée L1 p L2)
est une fonction f qui satisfait les conditions suivantes:

 Elle est calculable en temps polynomial,

 f(x)  L2 si et seulement si x  L1

 Conséquence : Si L2  P alors L1 est au plus aussi

difficile que L2

44
Réduction de Problèmes (2)
 Propriétés de  p :
 Si L1  p L2 alors
 Si L2 P alors L1 P
 Si L1 P alors L2  P
 Si L1  NP alors L2  NP

 Si L1  p L2 et L2  p L3
 L1  p L3

45
Réduction de Problèmes (3)
 Problèmes polynomialement équivalents
 Définition:
Deux langages L1 et L2 sont polynomialement équivalents (L1 p L2)
si et seulement si L1  p L2 et L2  p L1

 Classes d’équivalence polynomiale : soit tous les

membres sont dans P, soit aucun.

 Possibilité de construire une classe d’équivalence de

proche en proche.

46
Réduction de Problèmes (4)
 Structure de NP:
 Définition : Une classe d’équivalence polynomiale C1 est inférieure à une
classe d’équivalence C2 ( notation C1 C2 ) si  L1  C1 et L2  C2 : L1  p
L2

 P  NP ( P est la plus petite classe dans NP)

  L1 P et  L  NP on a L1  p L2

 Plus grande classe de NP : NP-Complets (noyau dur)

47
NP-Complétude (1)
 Langage NP-Complet :
 Définition : Un langage L est NP-Complet si
 L  NP
  L’  NP alors L’  p L ( Problème NP-Dur)
 Théorème : Soit L un langage NP-Complet,
L  P si et seulement si P = NP
 Un problème NP-Complet n’a de solution
polynomiale que si et seulement si P = NP

48
NP-Complétude (2)
 Problème de Satisfiabilité (SAT):
 Données :
 Un ensemble de variables booléennes {x1,x2,…xn}
 Un ensemble de clauses Ci = {y i,1  …… y i,r} où yi,j est
égal à l’un des xi soit à l’un des xi
 F = C1  C2  . . . .  Cm
 Résultat : Décider si F est satisfaisable (vraie)par une
affectation de valeurs de vérité V/F aux variables

49
NP-Complétude (3)
Stephen COOK
 Travaux sur SAT

 Reçoit le Turing Award en

1982

 Levin ( 1973) : travail

similaire sur le pavage

50
 NP-Complétude (4)
Théorème de Cook - Levin

Théorème :
SAT est NP-Complet

51
SAT & Co
 Problème k – SAT :
 Données :
 Un ensemble de variables booléennes {x1,x2,…xn}
 Un ensemble de clauses Ci = {y i,1  …… y i,k} où yi,j est
égal à l’un des xi soit à l’un des xi ( Ci = k )
 F = C1  C2  . . . .  Cm
 Résultat : Décider si F est satisfaisable par une
affectation de valeurs de vérité V/F aux variables

52
 Problèmes de Graphes NP-Complets (1)
Soit G (X,E ) un graphe d’ordre n

G est un graphe complet si :
 x1 et x2X : {x1,x2} E

 S  X est un stable de G si :
 x1 et x2S : {x1,x2} S

 T  X est un transversal de G si:

 e = {x1,x2} E : x1T ou x2 T

53
 Problèmes de Graphes NP-Complets (2)
Soit G (X,E ) un graphe d’ordre n :

 G X,F  est le graphe complémentaire de G :

{x1,x2} E  {x1,x2}  F

 S est une clique de G  S est sous-graphe complet de G

 S est une clique G (X,E )  S est stable de G X,F 

54
 Problèmes de Graphes NP-Complets (3)

Une coloration des sommets de G (X,E) est

une application :
C : X IN telle que C(v) ≠ C(w)  {v,w} E
 Une k - coloration est une coloration
utilisant k couleurs
 Le nombre chromatique (G) est défini par

(G) = Min { k / G est k –colorable}

G =3

55
Problèmes de Graphes NP-Complets (4)
 Stable ( Independant Set):

Données :
 Un graphe G(X,E) non orienté
 Un entier k

Résultat : Décider s’ un stable S  X , S k
 Clique

Données :
 Un graphe G(X,E) non orienté
 Un entier k

Résultat : Décider s’ une clique C  X , S  k

56
Problèmes de Graphes NP-Complets (5)
 Couverture de Sommets ( Vertex Cover):

Données :
 Un graphe G(X,E) non orienté
 Un entier k

Résultat : Décider s’ transversal T  X , S   k
 Coupure maximale ( Max Cut)
 Données :
 Un graphe G(X,E) non orienté
 Un entier k

Résultat : Décider s’ une partition X = X1 X2 telle que :
|{{x1,x2} E / x1 X1 et x2 X2 } |  k

57
Problèmes de Graphes NP-Complets (6)
 Circuit Hamiltonien ( HC):

Données :
 Un graphe G(X,E) non orienté

 Résultat : Existe-il un circuit hamiltonien dans G

 Circuit le plus long

Données :
 Un graphe G(X,E) non orienté
 Un entier k
 Résultat : Existe –il un cycle hamiltonien et dont
la longueur est  k ?

58
Problèmes de Graphes NP-Complets (7)
 Voyageur de Commerce
(TSP)
 Données : un couple ( n,M)
où M est une matrice d’ordre n
de réels et un réel B
 Réponse :
Existe-t-il une permutation  de
[1,n] telle que:

Allemagne ( 15 112 cités)

59
Problèmes de Graphes NP-Complets (8)
 k – Coloration ( k- Color)
 Données :
 Un graphe G(X,E) non orienté

Un entier k
 Résultat : Existe t-il une k-coloration de G ?

60
Somme de Sous-ensemble & Variantes (1)
 Somme de sous-ensemble ( Subset Sum)
 Données : E  IN , fini et un but t  IN

 Réponse : Existe-t-il E’  E tel que :

 xt
xE'
?

61
Somme de Sous-ensemble & Variantes(2 )
 Sac à Dos ( KnapSack)
 Données :
 Un ensemble de poids ai , i = 1,n
 Un ensemble de valeurs vi , i =1,n
 Un poids limite A et entier V
 Réponse : Existe-t-il une suite ci  {0,1}telle
que : n n

c a  A
i 1
i i et c v V
i 1
i i ?

62
Somme de Sous-ensemble & Variantes (3)
 Partition
 Données :
 Un ensemble A fini d’entiers
 Réponse : Existe-t-il A’  A tel que :

x  x
x A' x A A'
?

63
Somme de Sous-ensemble & Variantes (4)
 Rangement Optimal ( Bin Packing)
 Données :
 N objets de poids si
 Une capacité B et un entier k

 Réponse : Est-il possible de ranger les N objets

dans k boîtes de capacité B ?

64
Programmation Entière
 Programmation entière 0-1
 Données:
 Une matrice entière A (m,n)
 Un vecteur entier b d’ordre m

 Réponse : Existe-t-il un vecteur x d’ordre dont les éléments sont

pris dans {0,1} tel que : A x  b ?

65
Exemples de Réductions (1)
3-Sat  p Stable
 3-Sat  p 3-Color
HC  p Circuit le + long
VC  p Subset-Sum
Subset-Sum  p KnapSack
Subset-Sum  p Partition
3-Sat  p Prog. Entière
Partition  p Bin Packing

66
Exemples de Réduction (2)
 3-SAT est NP
 Soit I une instance de 3 –SAT , taille (I) = O( n+p)
 Certificat : valeur de chaque xi , i = 1, n
 Vérification en O(p)
 3 – SAT est NP-Dur : réduction à partir de SAT
 Soit I1 une instance de SAT
 n variables xi , i = 1, n
 p clauses Cj , j=1,p de longueur f(j)
 Taille(I1) = O( n +  f(j) )

67
Exemples de Réduction (3)
 Soit Ci une clause de SAT :

1 variable x : soient ai et bi deux nouvelles variables
 x  ai  bi ; x  ai  bi ; x  ai  bi ; x   ai  bi

2 variables x et y : soit ci une nouvelle variable :
 x  y  ci ; x  y   ci
 3 variables : aucun changement

k  3 variables : soit Ci = {x1  ……  xk} et soient yi,1 ,……
y i,,k- 3 ( k-3) nouvelles variables
 x  x  y
1 2 i,1 ;

 x   y  y
3 i,1 i,2 . . . . . . .

 xk -2   yi,k - 4  yi,k – 3 et xk -1   yi,k - 3  x,k

68
Exemples de Réduction (4)
 Taille (I2) linéaire en taille(I1) ,
 () Si I1 a une solution i.e. une instanciation des
variables xj telle que  j Cj soit vraie.

Une solution pour I2 est :
 xj inchangée
 ai vrai
 bi faux
 ci vrai
 Soit z1 ,…… zk des littéraux et zi le 1er littéral vrai alors on
pose z1 ,. . ., zi-2 à vrai et zi-1 ,…… zk-3 à faux.
 () si I2 a une solution :

Instanciation de I2 vraie restreinte aux xj i=1,n donne une
instanciation qui satisfait I1

69
Exemples de Réduction(5)
 Données: graphe G = (V,E) et un k  |V|.

 Clique (CLQ): Existe-t-il C  V avec |C|  k et (u,v)  E

pour tous u,v  C?

 Ensemble indépendant (IS): Existe-t-il C  V avec |C|  k

et (u,v)  E pour tous u,v  C?

 Couverture par sommets (VC): Existe-t-il C  V avec |C| 

k et tel que pour tout (u,v)  E, on a u  C ou v  C?

70
Exemples de Réductions (6)
Théorème: CLQ p IS p VC.

 Idée: montrer que ces trois problèmes ne sont que des

reformulations les uns des autres.
 L’existence d’une grande clique est équivalente à
l’existence d’un grand ensemble indépendant dans le
complément du graphe.
 L’existence d’un grand ensemble indépendant est
équivalente à l’existence d’une petite couverture par
sommets.

71
Exemples de Réductions (7)
 CLQ <p IS.

 Pour le démontrer formellement, on veut définir

une fonction f permet de transformer en temps
polynomial chaque instance G, k du problème
Clique en une instance f(G, k) = G’, k’ du
problème Ensemble Indépendant de telle sorte que
G, k  CLQ  G’, k’  IS.

72
 Exemples de Réductions (7)
 CLQ p IS.

Instance de IS:
Instance de CLQ: Gc = (V,Ec), graphe
Graphe G = (V,E) complément de G.
Entier k Entier k (inchangé)

Transformation f

73
 Exemples de Réductions (8)

À montrer:
1. f est calculable en évident
temps polynomial.
2. G,k  CLQ  G c,k Un ensemble de sommets forme
 IS. une clique dans G ssi il forme
un ensemble indépendant dans
G c.

74
 Exemples de Réduction (9)
 IS p VC.

Instance de VC:
Instance de IS: G = (V,E) (inchangé)
Graphe G = (V,E) Entier |V| - k
Entier k

Transformation f

75
 Exemple de Réduction (10)
À montrer:
1. f est calculable en temps polynomial. évident

2. G,k  IS  G, |V| - k  VC.

a)  G,k   IS   G, |V| - k   VC:

Si V’ est un IS de taille k, alors toutes les arêtes de E
ont au moins une extrémité dans V – V’. Donc V – V’
est une VC de taille |V| - k.
b)  G,k   IS   G, |V| - k   VC:
Si V’ est une VC de taille |V| - k, alors V – V’ est
un IS de taille k.

76
 Exemples de Réduction (11)
3-SAT p IS
Instance de IS : Graphe G = (V,E)
Occurrence d’un littéral  sommet
dans G.
Instance de 3-SAT  Arête entre deux sommets lij, li’j’ si
Variables X = x1, …, x les littéraux sont dans une même
n
m clauses Cj = l1j  l2j  l3j clause ou si sont contradictoires
Entier m (nombre de clauses)

77
 Exemples de Réduction (12)
x1 x2 x3
x1  x2  x3
x2 x3 x4
x2  x3  x4

x1  x2  x4 x1 x2 x4

La transformation se fait en temps O(m2). (borne supérieure de |E|).

Reste le plus dur : montrer que   3-SAT  G, m  IS.

78
 Exemple de Réduction (13)
Étape 1:   3-SAT  G, m  IS
x1 = 0, x2 = 1, x3 = 0, x4 = 1

x1  x2  x3 x1 x2 x3

x2  x3  x4 x2 x3 x4

x1  x2  x4 x1 x2 x4

 Chaque clause contient un littéral dont la valeur est 1 (Vrai).

Les sommets correspondants forment un IS de taille m car les

littéraux correspondants sont de clause différentes et non-
contradictoires 79
 Exemples de Réduction (14)
Étape 2: G, m  IS    3-SAT
x1 = 1, x2 = 1, x3 = 0, x4 = 1

x1  x2  x3 x1 x2 x3

x2  x3  x4 x2 x3 x4

x1  x2  x4 x1 x2 x4

80
 P = NP ?
 Pas de solution polynomiale pour un
problème NP-Complet
 On ne sait pas si les problèmes de
NP sont polynomiaux ou s’il existe
certains qui sont difficiles d’où
 P = NP ?

 Soit P  NP

 Soit P=NP ? n’est pas

décidable

81
 Liste de Garey & Johnson
Théorie des graphes (65 problèmes)
3-COL, domination, cycle Hamiltonien, etc.

Conception de réseau (51)

TSP, Max-cut, plus long chemin, etc.

Ensembles et partitions (21)

Formation d’équipes, partition

Logique (19), Planification (22), archivage (36), programmation mathématique (13),

algèbre (18), jeux et puzzles (15), automates et langages (21), optimisation de code (20),
autres (19)

Problèmes qu’on n’arrive à placer ni dans P ni NP-complets . Plus que 3!

82
Que faire face à un problème NP?(1)
 Si on a à résoudre un problème NP, on a les
deux options suivantes :
 Soit le problème est facile et on cherche à
exhiber une résolution polynomiale,
 Soit que le problème est difficile et on cherche
à démontrer qu’il est NP-Complet (par
réduction).

83
Que faire face à un problème NP?(2)
 Si on a à résoudre un problème NP-Complet, on peut :
 Chercher à donner une résolution polynomiale

 Vérifier que l’on est pas, intéressé par une instance

polynomiale
 Appliquer des schémas de résolution algorithmique

efficaces
 Diviser pour régner
 Programmation Dynamique
 Mettre en œuvre des algorithmes approchés, avec
garantie de performance.
 Utiliser des approches à base de machines parallèles

84
Classe de Complexité Co-NP (1)
 Les problèmes de P ont des solutions faciles à
trouver (algorithmes polynomiaux)

 Les problèmes de NP ont des solutions faciles à

vérifier

 Puisqu’on est autoriser à « regarder » la réponse,

 Comment un problème peut ne pas appartenir à NP ?

85
Classe de Complexité Co-NP(2)
 Exemple :

 Données : un couple ( n,M) où M est une matrice d’ordre n de réels et un réel B

 Réponse :

Est –il vrai qu’il n’existe pas une permutation  de [1,n] telle que :

Ce problème appartient – il à NP ?

86
Classe de Complexité Co-NP (3)
 Complémentaire d’un problème de décision 
noté C :
 DC = D
 YC = N
 NC = Y
 P = co-P
 Définition : La classe Co –NP est l’ensemble des
compléments des langages appartenant à NP i.e.
Co-NP = { L / LC  NP }

87
 Classe de Complexité Co-NP (4)
 Données : G(X,E) un
graphe
 Résultat : G est –il
hamiltonien ?
 Ce problème appartient
à Co-NP
 Appartient – il à NP ?

88
Classe de Complexité Co-NP (5)
 Théorème : Soit L NP- complet, si LC est NP
alors co-NP = NP

 Conjecture : NP  co-NP

 Théorème : Si NP  co-NP alors P  NP

89
Relations entre les classes de Complexité

90