Théorie de la complexité
Martin C. Cooper
IRIT, Université de Toulouse 3
Master2 DC - Modèles de Décision et de Raisonnemment
Martin C. Cooper Théorie de la complexité
Théorie de la complexité : Introduction
Le but de la théorie de la complexité est de pouvoir dire si un
problème est (ou non) soluble efficacement par un ordinateur.
Exemples de problèmes :
1 Etant donnés les pièces d’un puzzle P, reconstituer le
puzzle.
2 Déterminer si un nombre à n chiffres est premier ou non.
3 Etant donnée une équation diophantine ([Link].
xy 2 z + 7 = z 3 ) déterminer s’il existe une solution sur les
entiers
Un de ces problèmes ne peut être résolu par ordinateur, un est
“difficile" et un est “facile".
Martin C. Cooper Théorie de la complexité
Théorie de la complexité : Introduction
Le but de la théorie de la complexité est de pouvoir dire si un
problème est (ou non) soluble efficacement par un ordinateur.
Exemples de problèmes :
1 Etant donnés les pièces d’un puzzle P, reconstituer le
puzzle.
2 Déterminer si un nombre à n chiffres est premier ou non.
3 Etant donnée une équation diophantine ([Link].
xy 2 z + 7 = z 3 ) déterminer s’il existe une solution sur les
entiers
Un de ces problèmes ne peut être résolu par ordinateur (3), un
est “difficile" (1) et un est “facile" (2).
Martin C. Cooper Théorie de la complexité
Références bibliographiques
D. Bovet & P. Crescenzi, “Introduction to the Theory of
Complexity"
C.H. Papadimitriou, “Computational Complexity"
M. Garey & D.S. Johnson, “Computers and Intractability: A
Guide to the Theory of NP-Completeness"
Martin C. Cooper Théorie de la complexité
Modèle de Calcul
ENTREE SORTIE
- PROCESSUS -
une séquence soit oui/non
de symboles (problèmes de décision)
appartenant à
soit une séquence de
un alphabet Σ
symboles appartenant à Σ
([Link]. problèmes
d’optimisation)
Martin C. Cooper Théorie de la complexité
Problèmes de décision et problèmes fonctions
Pour définir un problème de décision, il suffit de décrire une
instance générique ainsi qu’une question oui-non sur chaque
instance.
Pour définir un problème fonction, il faut décrire une instance
générique ainsi qu’une relation de la forme
R = {hI, soli|sol est une solution possible pour l’instance I}.
(On cherche un algorithme qui réalise une fonction (partielle) f
qui retourne une solution f (I) telle que hI, f (I)i ∈ R lorsqu’une
solution existe).
Martin C. Cooper Théorie de la complexité
Exemples de problèmes de décision
CLIQUE
Instance: Un graphe G et un entier k .
Question: Existe-il dans G un graphe complet de k sommets?
COLORIAGE DE GRAPHES
Instance: Un graphe G et un entier k .
Question: Est-ce que G possède un coloriage de k couleurs
(une affectation de couleurs aux sommets telle que les
sommets adjacents soient de couleurs différentes)?
Martin C. Cooper Théorie de la complexité
Exemples de problèmes de décision
VOYAGEUR DE COMMERCE (D) (version Décision)
Instance: Un ensemble de villes {v1 , . . . , vn }, une distance
entière d(i, j) entre chaque paire de villes vi , vj et un entier B.
Question: Existe-il une permutation π de {1, . . . , n} telle que
n−1
!
X
d(π(i), π(i + 1)) + d(π(n), π(1)) ≤ B
i=1
Martin C. Cooper Théorie de la complexité
Complexité d’un algorithme
Dans la plupart des cas, c’est le temps de calcul excessif qui
limite l’utilisation de certains algorithmes =⇒ la mesure de
complexité le plus utile, c’est la complexité temporelle.
Définition
La complexité temporelle d’un algorithme A est la fonction
TempsA où TempsA (x) = nombre d’instructions exécutées
pendant le calcul A(x).
Martin C. Cooper Théorie de la complexité
Complexité d’un problème
On aimerait définir la complexité temporelle d’un problème Π
comme étant la complexité temporelle de l’algorithme A le plus
efficace pour résoudre Π, mais ... il est possible de démontrer
qu’on peut toujours rendre un algorithme A plus efficace.
=⇒ la complexité temporelle doit être asymptotique.
Définition
Pour toute fonction f , la complexité temporelle d’un langage L
est en O(f ) s’il existe un algorithme A qui décide L et des
constantes n0 , c telles que
∀x |x| > n0 =⇒ TempsA (x) ≤ cf (|x|)
Martin C. Cooper Théorie de la complexité
Classes de complexité
Définition
La classe (de complexité temporelle) TEMPS[f ] est la classe
de tous les langages de complexité temporelle en O(f ).
TEMPS[n] ⊆ TEMPS[n log n] ⊆ TEMPS[n2 ] ⊆
TEMPS[2n ] . . .
Martin C. Cooper Théorie de la complexité
Complexité polynomiale
Définition
P = k ≥0 TEMPS[nk ]
S
N.B. TEMPS[p(n)] ⊆ P pour tout polynôme p(n).
La classe P est identique pour les différents modèles de calcul
(machine de Turing, machine RAM, etc.) La définition de P est
aussi indépendante des détails du système de codage (tels que
la structure de données qu’on utilise pour stocker un graphe).
Est-ce que P = traitable ("tractable")?
Ce n’est pas le cas si le degré du polynôme est trop élevé ou si
les constantes sont trop grandes.
Martin C. Cooper Théorie de la complexité
k SAT
k -SATISFIABILITÉ
Instance: Une formule f en k -FNC (f est en FNC et comporte
au plus k littéraux par clause).
Question: Est-ce que f est satisfiable?
Théorème
2SAT ∈ P
Martin C. Cooper Théorie de la complexité
Algorithme de complexité polynomiale pour 2SAT :
(* Au départ, affectations = ∅ et res = "oui" *)
tant que ∃ une variable x non-affectée et res = "oui" faire
pour val = vrai..faux faire
effectuer les affectation dans affectations ∪ (x ← val);
res := Propager () ;
si res = "oui" alors quitter boucle pour
(* On a une affectation à un sous-ensemble des
variables qui est indépendante du reste des clauses *)
Propager () : tant que ∃ une clause li ∨ lj à propager
si li = lj = faux alors renvois "non" ;
si li = faux et lj non-affectée alors lj := vrai ;
si lj = faux et li non-affectée alors li := vrai ;
fin-tantque ;
ajouter les nouvelles affectations à affectations ;
renvois "oui";
Martin C. Cooper Théorie de la complexité
Réductions polynomiales
Une autre façon de démontrer qu’un problème Π1 appartient à
P, c’est de montrer une réduction vers un problème Π2 ∈ P.
Définition
(Karp 1972) Il y a une réduction polynomiale du langage L1
vers le langage L2 (on écrit L1 ≤ L2 ) s’il existe une fonction f de
complexité polynomiale telle que x ∈ L1 ssi f (x) ∈ L2 .
' $
' $ ' $
x f (x)
• - • L1 ≤ L2
& % & %
L1 & %
L2
Martin C. Cooper Théorie de la complexité
2-COLORIAGE ∈ P
Théorème
2-COLORIAGE ≤ 2-SAT
Voici une réduction polynomiale:
Pour chaque sommet vi du graphe, on crée une variable xi
Pour chaque arête {vi , vj } du graphe, on ajoute 2 clauses
(xi ∨ xj ) et (¬xi ∨ ¬xj ).
Soit f (vi ) = rouge si xi = vrai et f (vi ) = vert si xi = faux.
f est un 2-coloriage du graphe ssi l’affectation (x1 , . . . , xn )
satisfait toutes les clauses 2-SAT.
Cette réduction est évidement polynomiale.
Martin C. Cooper Théorie de la complexité
La classe NP : motivation
2-SAT ∈ P, 2-COLORIAGE ∈ P
Aucun algorithme de complexité polynomiale est connue
pour 3-SAT et 3-COLORIAGE
Par contre, il existe des algorithmes de complexité
polynomiale pour vérifier si une solution est correcte.
Martin C. Cooper Théorie de la complexité
Vérificateurs et la classe NP
Définition
Un algorithme A est un vérificateur pour un langage L si A
décide un langage L0 et L = {I | ∃s tel que (I, s) ∈ L0 }.
(Autrement dit, A décide si s est une solution pour l’instance I).
Définition
NP = la classe de langages qui possèdent un
vérificateur de complexité polynomiale.
Martin C. Cooper Théorie de la complexité
Exemples de problèmes en NP :
SATISFIABILITÉ, VOYAGEUR DE COMMERCE(D),
k -COLORIAGE, CLIQUE ∈ NP
Dans chaque cas, on peut vérifier en temps polynomial la
correction d’une solution.
Remarque
Le nom NP vient de "Nondeterministic Polynomial-time" [Karp
1972] i.e. complexité polynomiale sur une machine
non-déterministe (≈ une machine qui essaie toutes les
possibilités en même temps) ≡ ∃ un vérificateur de complexité
polynomiale.
La question P=NP? reste encore ouverte après 35 ans d’effort.
La résolution de ce problème vous fera gagner $1 000 000
([Link]
Martin C. Cooper Théorie de la complexité
Les classes FP et FNP
Pour les problemes fonction, il existe des classes équivalentes
à P et NP : FP et FNP.
Définition
Un problème fonction avec relation binaire associée R(I, sol)
appartient à FP s’il existe un algorithme A de complexité
polynomiale tel que ∀I, A(I) renvoit sol telle que R(I, sol) est
vrai (ou “non” si une telle sol n’existe pas).
Définition
Un problème fonction avec relation binaire associée R(I, sol)
appartient à FNP si, étant données I et sol, on peut vérifier
R(I, sol) en temps polynomial.
FP 6= FNP ⇔ P 6= NP
Martin C. Cooper Théorie de la complexité
NP-complétude
Les réductions polynomiales L1 ≤ L2 définissent un ordre
partiel entre les problèmes de décision.
Définition
Un langage L ∈ NP est NP-complet si L0 ≤ L pour tout L0 ∈ NP.
Les problèmes NP-complets sont tous aussi difficiles les uns
que les autres, dans le sens qu’un algorithme efficace pour un
langage NP-complet L fournirait un algorithme efficace pour
tout L0 ∈ NP.
' $
' NP $
#
P NP-complet décidable
"!
& %
& %
Martin C. Cooper Théorie de la complexité
Comment démontrer qu’un problème est NP-complet
Pour démontrer que L est NP-complet, il suffit de démontrer
que L ∈ NP et L0 ≤ L pour un langage NP-complet L0 .
Donc, le plus difficile c’est de trouver le premier langage
NP-complet L0 .
Martin C. Cooper Théorie de la complexité
Le théorème de Cook
Théorème (Cook 1972)
SATISFIABILITÉ est NP-complet
Principe de la preuve:
1 pour chaque problème Π ∈ NP, il existe un programme de
vérification P qui renvoit "oui" si l’entrée S est une solution
pour une instance I et "non" sinon.
2 on peut coder l’exécution correcte de P sur (I, S) avec
résultat "oui" comme une instance AI,P de SAT avec
variables Vijk = vrai si l’adresse i contient j après k
opérations. (S fait partie des variables).
3 AI,P satisfiable ⇔ ∃ solution S pour I. Donc Π ≤ SAT.
Martin C. Cooper Théorie de la complexité
Preuves de NP-complétude
Pour démontrer qu’un problème Π est NP-complet, il suffit de
1 démontrer que Π ∈ NP
2 démontrer que Π0 ≤ Π pour un problème NP-complet Π0 .
Voir le livre de Garey & Johnson pour une liste de centaines de
problèmes NP-complets.
N.B. Si Π0 ≤ Π pour un problème NP-complet Π0 , mais on ne
sait pas si Π ∈ NP, alors on dit que Π est NP-difficile (NP-dur).
Martin C. Cooper Théorie de la complexité
CSP ∈ NP-complet
Théorème
CSP est NP-complet
Preuve: CSP ∈ NP et SAT ≤ CSP car SAT est un
sous-problème de CSP.
Martin C. Cooper Théorie de la complexité
3SAT ∈ NP-complet
Théorème
3SAT est NP-complet
Preuve: Puisque 3SAT ∈ NP, il suffit de démontrer que
SATISFIABILITÉ ≤ 3SAT.
Remplacer chaque clause C = x1 ∨ x2 ∨ . . . ∨ xk (avec
k > 3) par
C 0 = (x1 ∨x2 ∨y1 )∧(¬y1 ∨x3 ∨y2 )∧. . .∧(¬yk −3 ∨xk −1 ∨xk )
C est satisfiable ssi C 0 est satisfaible
(car ∃y1 , . . . , yk −3 C 0 = vrai ⇔ au moins un des xi est vrai
⇔ C est vraie)
Martin C. Cooper Théorie de la complexité
COLORIAGE est NP-complet
Théorème
COLORIAGE DE GRAPHES est NP-complet
Preuve:
1 COLORIAGE DE GRAPHES ∈ NP
2 3SAT ≤ COLORIAGE DE GRAPHES
Pour une formule f = C1 ∧ . . . ∧ Ck
créer 3 sommets V , F , A, reliés par 3 arêtes. Sans perte de
généralité, on peut désigner les couleurs affectées aux
sommets V , F , A par les noms vrai, faux, autre
créer un sommet pour chaque littéral x ou ¬x, et ajouter un
sous-graphe qui impose col(x) ∈ {vrai, faux} et
col(x) 6= col(¬x)
pour chaque clause Ci de la forme x ∨ y ∨ z ajouter un
sous-graphe qui impose
(col(x), col(y ), col(z)) 6= (faux, faux, faux)
Martin C. Cooper Théorie de la complexité
Les sous-graphes nécessaires à la construction :
y ¬y x• •V
• • @
¬x B z @•
• B •
@ B @ •
x •PP @ B • ¬z
@
J
J
PP@
@•
PB •
J•
A A @
A V• • @• •z
• • • •
AA
V F y V
x, ¬x ∈ {vrai, faux} x ∨y ∨z
x 6= ¬x
Martin C. Cooper Théorie de la complexité
CLIQUE ∈ NP-complet
Théorème
CLIQUE est NP-complet
Preuve:
1 CLIQUE ∈ NP (car la liste des sommets est un certificat)
2 SATISFIABILITÉ ≤ CLIQUE
Pour une formule f = C1 ∧ . . . ∧ Ck
créer un sommet pour chaque paire (x, Cj ) où x est un
littéral de la clause Cj
créer une arête entre (x, Ci ) et (y , Cj ) si i 6= j et x, y sont
compatibles (x 6= ¬y ).
Cette construction se fait en temps polynomial. Le graphe ainsi
créé comporte une clique de taille k ssi f est satisfiable
(affecter la valeur vrai à chaque variable de la clique)
Martin C. Cooper Théorie de la complexité
Exemple de la construction :
(x ∨ y ∨ z) ∧ (¬x ∨ ¬a) ∧ (a ∨ b ∨ ¬y ∨ ¬z)
x H
h
PhPhhh (( a
S HH
PP hh (( (((
P
(( ((hh hhhhh
S H
( P
y Q (
( S
P
( HHPP
P
b
h
(
P
@QPPH((( PP((((
(x ∨ y ∨ z) @
QS
(P(P( ( HH P P (a ∨ b ∨ ¬y ∨ ¬z)
z Q
(
(
PP@
(Q S P P H
PPH
PP
¬y
QP@ PSQ H
P
P Q PH
P
Q @ SPP HP
Q SQ Q
P
Q@ ¬x
P ¬z
H
Q@S
Q@
Q
S
¬a
(¬x ∨ ¬a)
A partir de cette clique de taille k = 3, on trouve la solution x =
vrai, a = faux, b = vrai (y , z prennent n’importe quelle valeurs).
Martin C. Cooper Théorie de la complexité
coNP : les problèmes complémentaires
Définition
coNP est l’ensemble des langages qui ont pour
complémentaire (au sens des langages) un langage de NP :
coNP = {L | ¬L ∈ NP}
Autrement dit : coNP est l’ensemble des langages pour
lesquels une preuve vérifiable en temps polynomial peut
prouver la non-appartenance du mot au langage (les certificats
sont des contre-exemples et non des solutions).
Exemples : NON-CLIQUE (déterminer s’il n’existe pas de
clique de taille k dans un graphe G), UNSAT (déterminer si une
formule φ en FNC est insatisfiable).
Martin C. Cooper Théorie de la complexité
coNP-complétude
Définition
Un langage L0 est coNP-complet si
1 L0 ∈ coNP
2 Pour chaque L ∈ coNP, L ≤ L0 (il y a une réduction
polynomiale de L vers L0 ).
Martin C. Cooper Théorie de la complexité
coNP-complétude d’UNSAT
Théorème
UNSAT ∈ coNP-complet.
Preuve : Nous savons que UNSAT ∈ coNP.
Soit L ∈ coNP. Il faut démontrer L ≤ UNSAT. Il y a une réduction
polynomiale ¬L ≤ SAT (par la NP-complétude de SAT).
Puisque chaque instance de L est aussi une instance de ¬L
(c’est la question qui change mais pas l’instance), pour chaque
instance I de L, il existe une formule φI telle que
φI est satisfiable ssi I ∈ ¬L.
Donc φI est insatisfiable ssi I ∈ / ¬L.
Donc φI ∈ UNSAT ssi I ∈ L.
Martin C. Cooper Théorie de la complexité
Exemple d’un problème coNP-complet
TAUTOLOGIE
Instance: Une formule booléenne φ en FNC.
Question: Est-ce que φ = vrai pour toute affectation des
variables?
Théorème
TAUTOLOGIE ∈ coNP-complet.
Preuve : (1) On peut vérifier un contre exemple (une
affectation qui ne satisfait pas la formule) en temps polynomial.
(2) φ est une tautologie ssi ¬φ est insatisfiable, donc il y a une
réduction polynomiale UNSAT ≤ TAUTOLOGIE.
Martin C. Cooper Théorie de la complexité
Une autre définition de coNP
L ∈ NP si et seulement s’il existe une relation R ∈ P tel que
x ∈ L ssi ∃y , R(x, y ) = vrai.
L ∈ coNP si et seulement s’il existe une relation R ∈ P tell que
x ∈ L ssi ∀y , R(x, y ) = vrai.
Preuve : (L ∈ coNP) ⇔ (¬L ∈ NP) ⇔ (∃R 0 ∈ P tel que x ∈ ¬L
ssi ∃y , R 0 (x, y ) = vrai) ⇔ (∃R = ¬R 0 ∈ P tel que x ∈ L ssi ∀y ,
R(x, y ) = vrai).
Martin C. Cooper Théorie de la complexité
Au delà de NP et coNP
Définition
Σi est la classe des langages L tels que ∃ une relation R ∈ P
telle que x ∈ L ssi ∃y 1∀y 2 · · · Qi yi R(x, y 1, y 2, . . . , yi ), où
Qj = ∃ si j est impair et Qj = ∀ si j est pair.
Définition
Πi est la classe des langages L tels que ∃ une relation R ∈ P
telle que x ∈ L ssi ∀y 1∃y 2 · · · Qi yi R(x, y 1, y 2, . . . , yi ), où
Qj = ∀ si j est impair et Qj = ∃ si j est pair.
Interprétation en termes de jeu à 2 joueurs : un problème de Σi
peut être vu comme demander s’il existe une stratégie
gagnante en i coups pour le 1er joueur. De façon similaire, un
problème de Πi peut être vu comme demander s’il existe une
stratégie gagnante en i coups pour le 2ème joueur.
Martin C. Cooper Théorie de la complexité
La hiérarchie polynomiale
Définition (Polynomial Hierarchy)
[
PH = Σi
i
A partir de leurs définitions, nous avons directement :
Σ1 = NP
Π1 = coNP
Σi ⊆ Σi+1
Πi ⊆ Πi+1
Σi ⊆ Πi+1
Πi ⊆ Σi+1
Martin C. Cooper Théorie de la complexité
Complexité spatiale
En informatique, l’espace et le temps sont différents : on ne
peut pas réutiliser le temps!
Définition
PSPACE = la classe de problèmes de décision que l’on peut
résoudre en utilisant un espace mémoire de taille bornée par
une fonction polynomiale de la taille de l’instance.
Exemples : SAT, planification-STRIPS ∈ PSPACE.
P ⊆ PSPACE
P 6= PSPACE si P 6= NP.
Martin C. Cooper Théorie de la complexité
PSPACE-complétude
Définition
Un langage L est PSPACE-complet si
1 L ∈ PSPACE,
2 pour tout langage L0 ∈ PSPACE, L0 ≤ L.
QBF
Instance: Une formule booléenne φ en FNC et une séquence
de quantifications Q1 x1 , . . . , Qn xn sur les variables de φ, où
Qi ∈ {∀, ∃} (par exemple, ∀x1 ∃x2 ∀x3 ∃x4 ...φ).
Question: Est-ce que Q1 x1 , . . . , Qn xn φ = vrai ?
Théorème
QBF est PSPACE-complet.
Martin C. Cooper Théorie de la complexité
PSPACE et la hiérarchie polynomiale
Théorème
PH ⊆ PSPACE.
Remarque
Le problème PSPACE-complet QBF a une forme très similaire
aux langages dans PH, sauf que le nombre de quantificateurs
n n’est pas borné par une constante car c’est le nombre de
variables de l’instance.
Martin C. Cooper Théorie de la complexité
EXPTIME
Rappel : La classe TEMPS[f ] est la classe de tous les
langages de complexité temporelle en O(f ).
Définition
k
[
EXPTIME = TEMPS[2n ]
k ≥0
c’est-à-dire, l’ensemble de tous les problèmes qui peuvent être
résolus en temps exponentiel.
Exemple : Etant donné un programe P, une entrée E et un
entier N, déterminer si P(E) s’arrête en au plus N étapes.
Preuve : Executer N étapes de P(E) se fait en temps O(N), et
il faut O(log N) bits pour coder N.
Martin C. Cooper Théorie de la complexité
Complexté temporelle et complexité spatiale
Théorème
NP ⊆ PSPACE ⊆ EXPTIME.
Preuve :
1 Soit Π ∈ NP. Il existe un vérificateur A de complexité
polynomiale pour Π. Les solutions potentielles sont
forcément de taille polynomiale (car A doit les lire en temps
polynomial). Un algorithme qui appelle A sur chaque
solution possible utilise un espace mémoire polynomial.
Donc Π ∈ PSPACE.
2 Un algorithme qui utilise un espace mémoire de taille
polynomiale p(n) ne peut utiliser un temps de calcul
supérieur à 2p(n) (= le nombre total d’états possible de la
mémoire) sans boucler.
Martin C. Cooper Théorie de la complexité
Questions ouvertes :
P = NP ∩ coNP ? (pourrait être vrai)
P = NP ? (très peu probable que ce soit vrai)
NP = PSPACE ? (très peu probable que ce soit vrai)
PH = PSPACE ? (peu probable que ce soit vrai)
PSPACE = EXPTIME ? (peu probable que ce soit vrai)
Ce que l’on sait : P 6= EXPTIME.
Martin C. Cooper Théorie de la complexité
Problèmes d’optimisation
Définition
Un problème d’optimisation Π = (E, Sol, m, obj) sera défini par
Un ensemble E d’instances.
Une fonction Sol telle que pour tout I ∈ E, Sol(I)
représente l’ensemble des solutions réalisables (“feasible
solutions”) pour I.
Une fonction m à valeur entière définie sur tous les
couples I ∈ E et x ∈ Sol(I). Cette mesure m représente la
fonction objectif d’une solution x pour l’instance I.
Un objectif obj ∈ {min, max} précisant si Π est un
problème de minimisation ou de maximisation.
Martin C. Cooper Théorie de la complexité
La classe NPO ≈ problèmes d’optimisation dont le
problème de décision appartient à NP
Définition
Définition Un problème Π = (E, Sol, m, obj) d’optimisation
appartient à la classe NPO si :
Les instances I ∈ E peuvent être reconnues en temps
polynomial.
Il existe un polynôme p tel que pour tout I ∈ E et
x ∈ Sol(I), |x| ≤ p(|I|). De plus il est décidable en temps
polynomial si x ∈ Sol(I).
La mesure m est une fonction calculable en temps
polynomial en |I|.
Martin C. Cooper Théorie de la complexité
Exemple de problème dans NPO
SAC-A-DOS (KNAPSACK)
Instance: Un sac-à-dos de capacité C et un ensemble
d’objets O = {1, 2, . . . , n}, où chaque objet a un poids wi et une
valeur vi .
Problème : Trouver un sous ensemble M ⊆ O d’objets de
valeur totale maximale que l’on puisse transporter P dans le
sac-à-dos, c’est-à-dire qui maximise la valeur
P i∈M vi tel que
w
i∈M i ≤ C.
Pour une instance I :
Sol(I) = l’ensemble deP
solutions réalisables = les
ensembles M tels que i∈M wi ≤ C
P
m(I, M) = la measure de la solution M = i∈M vi
l’objectif obj = max
Martin C. Cooper Théorie de la complexité
Algorithmes d’approximation
Définition
Soit r (n) ≥ 1 une suite de valeurs réeles. Un algorithme A est
une r (n)-approximation pour le problème Π = (E, Sol, m, obj) si
Pour chaque instance I ∈ E, A retourne une solution
xA ∈ Sol(I).
De plus xA vérifie
m∗ (I)/r (|I|) ≤ m(I, xA ) ≤ m∗ (I)r (|I|)
où m∗ (I) est la valeur de la solution optimale.
On dit que r (n) est la garantie de performance de l’algorithme
A.
Martin C. Cooper Théorie de la complexité
APX
Définition
La classe APX est constituée des problèmes de NPO
admettant une O(1)-approximation A de complexité
polynomiale en |I|.
Exemple : MAX-SAT ∈ APX
Preuve : m(I, x) = nombre de clauses satisfaites par la
solution x.
Soit A l’algorithme qui retourne xA = la meilleure des deux
solutions (vrai, . . . , vrai) et (faux, . . . , faux). xA satisfait au
moins la moitié des clauses et donc m∗ (I)/2 ≤ m(I, xA ).
Donc A est une 2-approximation.
Martin C. Cooper Théorie de la complexité
Exemple d’un problème difficile à approximer
VOYAGEUR DE COMMERCE (version optimisation)
Instance: Un ensemble de villes {1, . . . , n} et une distance
entière d(i, j) entre chaque paire de villes i, j.
Problème: P Trouver une permutation π de {1, . . . , n} qui
minimise n−1 i=1 d(π(i), π(i + 1)) + d(π(n), π(1)).
Etant donné un graphe G = hS, Ai, on peut construire une
instance du problème de voyageur de commerce qui détermine
l’existence d’un chemin hamiltonien :
d(i, j) = 1 si {i, j} ∈ A et d(i, j) = 1 + n2 sinon.
∃ chemin hamiltonian dans G ⇔ ∃ tournée de longueur n
Une O(1)-approximation résoudrait le problème de chemin
hamiltonien en temps polynomial.
Donc, si P 6= NP, alors VOYAGEUR DE COMMERCE ∈ / APX.
Martin C. Cooper Théorie de la complexité
PTAS
Définition
Un schéma d’approximation polynomial (PTAS = “Polynomial
Time Approximation Scheme”) est une famille (A )>0
d’algorithmes polynomiaux en |I| telle que pour tout > 0,
A est une (1 + )-approximation.
Définition
La classe PTAS est constituée des problèmes de NPO
admettant un PTAS.
Martin C. Cooper Théorie de la complexité
FPTAS
Définition
Un schéma d’approximation pleinement polynomial (FPTAS =
“Fully Polynomial Time Approximation Scheme”) est un
algorithme A() polynomial en |I| et en 1/ tel que pour tout
> 0 fixé, A() est une (1 + )-approximation.
Définition
La classe FPTAS est constituée des problèmes de NPO
admettant un FPTAS.
Martin C. Cooper Théorie de la complexité
Exemple : SAC-A-DOS ∈ FPTAS
Il existe un algorithme (pseudo-polynomial) A de
programmation dynamique pour SAC-A-DOS de complexité
O(n2 V ) où V est la valeur maximale des objets.
Soit I une instance de SAC-A-DOS, dans laquelle les objets
1, . . . , n ont les valeurs v1 , . . . , vn .
Pour un > 0 donné, on construit une version reduite I de I
dans laquelle on remplace les valeurs vi par bnvi /V c.
L’algorithme de programmation dynamique A résoud I en
temps O(n2 (n/)) (donc polynomial en n et en 1/).
On peut démontrer que la solution optimale x pour I satisfait
m(I, x ) ≥ (1 − )m∗ (I)
Donc, A(I ) est une (1 + )-approximation pour SAC-A-DOS.
Martin C. Cooper Théorie de la complexité
Exemple : MIN-COLORIAGE DE GRAPHES
PLANAIRES ∈ / PTAS
MIN-COLORIAGE DE GRAPHES PLANAIRES
Instance: Un graphe planaire G
Problème : Trouver un coloriage de G qui minimise m(G) = le
nombre de couleurs.
1 Tout graphe planaire a un 4-coloriage.
2 Déterminer si un graphe planaire possède un 3-coloriage
est un problème NP-complet.
3 Donc, une (1 + )-approximation pour < 1/3 résoudrait
ce problème de décision en temps polynomial.
4 Donc, si P 6= NP, alors il ne peut exister de PTAS pour
MIN-COLORIAGE DE GRAPHES PLANAIRES.
Martin C. Cooper Théorie de la complexité
Inclusions des classes de complexité (de problèmes
d’optimisation)
' $
' NPO $
' APX $
PTAS
FPTAS
&& %%
& %
FPTAS 6= PTAS ⇔ PTAS 6= APX ⇔ APX 6= NPO
⇔ P 6= NP
Martin C. Cooper Théorie de la complexité