Complexité des problèmes#
Introduction#
Tout au long de ce livre, nous avons étudié des algorithmes efficaces — triant en O(n log n), cherchant en O(log n), parcourant des graphes en O(V+E). Mais une question fondamentale demeure : existe-t-il des problèmes pour lesquels aucun algorithme efficace n’est possible ? La théorie de la complexité s’attache à classifier les problèmes non pas selon l’efficacité d’un algorithme particulier, mais selon la difficulté intrinsèque du problème lui-même.
Cette discipline, née dans les années 1970, a révélé une frontière mystérieuse entre les problèmes solubles rapidement et ceux pour lesquels les meilleurs algorithmes connus requièrent un temps exponentiel. Comprendre cette frontière est essentiel pour tout informaticien : cela permet de savoir quand chercher un algorithme polynomial, quand se contenter d’une approximation, et quand le problème est fondamentalement insoluble.
Classes de complexité P et NP#
La théorie de la complexité s’appuie sur la notion de machine de Turing comme modèle de calcul universel. Nous travaillerons avec des problèmes de décision — des problèmes dont la réponse est « oui » ou « non » — car ils sont plus simples à classifier que les problèmes d’optimisation (bien que les deux soient étroitement liés).
Définition 100 (Classe P)
La classe P (Polynomial time) est l’ensemble des problèmes de décision solubles par un algorithme déterministe en temps polynomial en la taille de l’entrée. Formellement, un problème L est dans P s’il existe un algorithme A et un polynôme p tels que, pour toute entrée x de taille n, A répond correctement en au plus p(n) étapes.
Exemples : tri (décider si un tableau est trié), recherche, plus court chemin, arbre couvrant minimal, 2-colorabilité d’un graphe, programmation linéaire.
Définition 101 (Classe NP)
La classe NP (Nondeterministic Polynomial time) est l’ensemble des problèmes de décision pour lesquels une réponse « oui » peut être vérifiée en temps polynomial à partir d’un certificat (ou témoin) de taille polynomiale.
Formellement, un problème L est dans NP s’il existe un vérificateur V (algorithme polynomial) tel que : pour toute instance x avec réponse « oui », il existe un certificat c de taille polynomiale vérifiant V(x, c) = « oui » ; pour toute instance x avec réponse « non », il n’existe pas de tel certificat.
Exemples : satisfaisabilité booléenne (le certificat est une assignation satisfaisante), clique (le certificat est la clique), coloration de graphe, problème du voyageur de commerce (le certificat est une tournée).
Remarque 45
P ⊆ NP. Tout problème dans P est aussi dans NP : si on peut résoudre un problème en temps polynomial, on peut certainement vérifier une solution en temps polynomial (il suffit de la recalculer).
La grande question ouverte est : P = NP ? Si c’était le cas, tout problème dont la solution est vérifiable rapidement serait aussi soluble rapidement. Si P ≠ NP (ce que la plupart des informaticiens croient), il existerait des problèmes NP qui ne sont pas dans P — des problèmes dont on peut vérifier les solutions efficacement mais qu’on ne sait pas résoudre efficacement.
La question P = NP#
La question de l’égalité entre P et NP est l’un des sept problèmes du millénaire de l’Institut Clay, assortie d’une récompense d’un million de dollars. Posée formellement par Stephen Cook en 1971, elle demeure sans réponse plus de cinquante ans plus tard.
Remarque 46
Enjeux de la question P = NP.
Si P = NP :
La cryptographie à clé publique (RSA, HTTPS) s’effondrerait : factoriser un nombre serait aussi facile que de multiplier.
Les problèmes d’optimisation combinatoire (planification, logistique, conception de médicaments) deviendraient tractables.
L’intelligence artificielle ferait un bond prodigieux : prouver des théorèmes mathématiques, comprendre le langage naturel, seraient solubles polynomialement.
Si P ≠ NP (cas probable) :
Il existe une hiérarchie de problèmes intrinsèquement difficiles.
La cryptographie moderne est fondée sur des bases solides.
Les heuristiques et les approximations restent indispensables pour les problèmes NP-difficiles.
Malgré des décennies d’efforts, personne n’a réussi à prouver que P ≠ NP. Les meilleurs algorithmes connus pour les problèmes NP-complets sont exponentiels, mais cela ne prouve pas l’inexistence d’algorithmes polynomiaux.
NP-complétude et réductions#
Le concept de NP-complétude formalise l’idée qu’il existe des problèmes NP « les plus difficiles » — tels que résoudre l’un d’eux polynomialement permettrait de résoudre tous les problèmes NP polynomialement.
Définition 102 (Réduction polynomiale)
Un problème A est polynomialement réductible à un problème B (noté A ≤_P B) s’il existe un algorithme polynomial f qui transforme toute instance x de A en une instance f(x) de B, de sorte que x est une instance « oui » de A si et seulement si f(x) est une instance « oui » de B.
Intuitivement, si A ≤_P B, alors B est au moins aussi difficile que A : si on sait résoudre B en temps polynomial, on sait résoudre A en temps polynomial.
Définition 103 (NP-complétude)
Un problème L est NP-complet si :
L est dans NP (une solution peut être vérifiée en temps polynomial).
Tout problème de NP est polynomialement réductible à L (L est NP-difficile).
Un problème est NP-difficile s’il satisfait la condition 2 mais pas nécessairement la condition 1 (il peut ne pas être dans NP, par exemple si c’est un problème d’optimisation plutôt que de décision).
Remarque 47
Théorème de Cook-Levin (1971). Le problème SAT (satisfaisabilité booléenne) est NP-complet. C’est le premier problème prouvé NP-complet. La preuve consiste à montrer que n’importe quelle machine de Turing non déterministe polynomiale peut être simulée par une formule booléenne satisfaisable si et seulement si la machine accepte.
Une fois qu’on dispose d’un problème NP-complet de référence, on peut en déduire d’autres par réduction : pour montrer que B est NP-complet, il suffit de montrer que B est dans NP et qu’un problème NP-complet connu A se réduit polynomialement à B (A ≤_P B).
Problèmes NP-complets célèbres#
Exemple 13 (Problèmes NP-complets classiques)
3-SAT. Étant donné une formule booléenne en forme normale conjonctive (conjonction de clauses, chaque clause ayant exactement 3 littéraux), existe-t-il une assignation des variables qui satisfait la formule ? 3-SAT est NP-complet (Karp, 1972), mais 2-SAT est dans P.
Problème de la clique. Étant donné un graphe G et un entier k, existe-t-il un sous-ensemble de k sommets mutuellement adjacents (une clique de taille k) ?
Coloration de graphe. Étant donné un graphe G et un entier k, peut-on colorier les sommets avec k couleurs de sorte que deux sommets adjacents aient des couleurs différentes ? Pour k ≥ 3, le problème est NP-complet ; pour k = 2, il est dans P (test de bipartitité).
Problème du voyageur de commerce (TSP). Étant donné un graphe complet pondéré et un budget B, existe-t-il une tournée hamiltonienne de coût ≤ B ? NP-complet même pour les graphes métriques.
Problème du sac à dos (0/1). Étant donné des objets de poids et valeurs, une capacité W et un seuil V, peut-on choisir des objets de poids total ≤ W et de valeur ≥ V ?
def est_3sat_satisfaisable_force_brute(clauses, n_variables):
"""
Vérifie par force brute si une instance de 3-SAT est satisfaisable.
clauses : liste de listes de littéraux (entier positif = variable, négatif = négation)
n_variables : nombre de variables
Complexité : O(2^n · |clauses|)
"""
def evaluer(assignation, clause):
return any(
(assignation[abs(lit) - 1] if lit > 0 else not assignation[abs(lit) - 1])
for lit in clause
)
for bits in itertools.product([False, True], repeat=n_variables):
if all(evaluer(bits, clause) for clause in clauses):
# Trouver le certificat
return True, {f'x{i+1}': bits[i] for i in range(n_variables)}
return False, {}
# Instance satisfaisable : (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ x3 ∨ x4) ∧ (x2 ∨ ¬x3 ∨ x4) ∧ (¬x2 ∨ x3 ∨ ¬x4)
clauses_sat = [[1, 2, -3], [-1, 3, 4], [2, -3, 4], [-2, 3, -4]]
sat, certificat = est_3sat_satisfaisable_force_brute(clauses_sat, 4)
print(f"Instance satisfaisable : {sat}")
if sat:
print(f"Certificat : {certificat}")
print(f"Vérification : ", end='')
for c in clauses_sat:
val = any((certificat[f'x{abs(l)}'] if l > 0 else not certificat[f'x{abs(l)}']) for l in c)
print(f"{val}", end=' ')
print()
# Instance non satisfaisable : (x1 ∨ x1 ∨ x1) ∧ (¬x1 ∨ ¬x1 ∨ ¬x1)... cas trivial
clauses_unsat = [[1, 1, 1], [-1, -1, -1]]
unsat, _ = est_3sat_satisfaisable_force_brute(clauses_unsat, 1)
print(f"\nInstance non satisfaisable : {not unsat}")
# Illustration du temps exponentiel
print("\n--- Temps de résolution par force brute ---")
for n_vars in range(5, 22, 2):
# Générer une instance aléatoire (satisfaisable)
import random
random.seed(42)
clauses_test = [[random.choice([-1, 1]) * random.randint(1, n_vars) for _ in range(3)]
for _ in range(n_vars * 3)]
t0 = time.perf_counter()
sat_test, _ = est_3sat_satisfaisable_force_brute(clauses_test, n_vars)
dt = time.perf_counter() - t0
print(f" n={n_vars:2d} variables : {2**n_vars:8d} assignations, {dt*1000:.2f} ms")
if dt > 0.5:
print(" (arrêt : trop lent)")
break
Instance satisfaisable : True
Certificat : {'x1': False, 'x2': False, 'x3': False, 'x4': False}
Vérification : True True True True
Instance non satisfaisable : True
--- Temps de résolution par force brute ---
n= 5 variables : 32 assignations, 0.05 ms
n= 7 variables : 128 assignations, 0.11 ms
n= 9 variables : 512 assignations, 1.19 ms
n=11 variables : 2048 assignations, 3.74 ms
n=13 variables : 8192 assignations, 0.38 ms
n=15 variables : 32768 assignations, 22.26 ms
n=17 variables : 131072 assignations, 284.25 ms
n=19 variables : 524288 assignations, 42.97 ms
n=21 variables : 2097152 assignations, 257.89 ms
Stratégies face aux problèmes NP-difficiles#
Lorsqu’on est confronté à un problème NP-difficile en pratique, plusieurs stratégies sont disponibles selon les contraintes.
Algorithmes d’approximation#
Définition 104 (Algorithme d’approximation)
Un algorithme d’approximation à facteur α pour un problème de minimisation produit une solution de coût au plus α fois le coût optimal, pour toute instance. On dit que l’algorithme est une α-approximation (avec α ≥ 1). Pour les problèmes de maximisation, le facteur α ≤ 1.
def vertex_cover_approximation(graphe, n_sommets):
"""
Algorithme d'approximation 2 pour le vertex cover.
Algorithme : tant qu'il existe une arête non couverte, ajouter ses deux extrémités.
Garantie : la solution retournée a au plus 2× la taille optimale.
"""
couverture = set()
aretes_restantes = list(graphe)
while aretes_restantes:
# Prendre une arête arbitraire
u, v = aretes_restantes.pop()
couverture.add(u)
couverture.add(v)
# Retirer toutes les arêtes couvertes
aretes_restantes = [(a, b) for a, b in aretes_restantes
if a not in couverture and b not in couverture]
return couverture
def tsp_approximation_2opt(distances, n):
"""
Heuristique 2-opt pour le TSP métrique.
Commence par une tournée gloutonne, puis améliore par échanges 2-opt.
"""
# Tournée initiale greedy (voisin le plus proche)
non_visites = set(range(1, n))
tournee = [0]
courant = 0
while non_visites:
suivant = min(non_visites, key=lambda v: distances[courant][v])
tournee.append(suivant)
non_visites.remove(suivant)
courant = suivant
tournee.append(0)
def cout_tournee(t):
return sum(distances[t[i]][t[i+1]] for i in range(len(t) - 1))
# Amélioration 2-opt
ameliore = True
while ameliore:
ameliore = False
for i in range(1, n - 1):
for j in range(i + 1, n):
# Essayer d'inverser le segment [i, j]
nouvelle_tournee = tournee[:i] + list(reversed(tournee[i:j+1])) + tournee[j+1:]
if cout_tournee(nouvelle_tournee) < cout_tournee(tournee):
tournee = nouvelle_tournee
ameliore = True
return tournee, cout_tournee(tournee)
# Exemple Vertex Cover
graphe = [(0,1), (1,2), (2,3), (3,0), (0,2)]
couverture = vertex_cover_approximation(graphe, 4)
print(f"Graphe : {graphe}")
print(f"Vertex Cover approx (2-approx) : {couverture} (taille {len(couverture)})")
# Exemple TSP
import random
random.seed(42)
n_villes = 8
coords = [(random.randint(0, 100), random.randint(0, 100)) for _ in range(n_villes)]
distances = [[int(((coords[i][0]-coords[j][0])**2 + (coords[i][1]-coords[j][1])**2)**0.5)
for j in range(n_villes)] for i in range(n_villes)]
tournee, cout = tsp_approximation_2opt(distances, n_villes)
print(f"\nTSP 2-opt ({n_villes} villes) :")
print(f" Tournée : {' → '.join(map(str, tournee))}")
print(f" Coût : {cout}")
Graphe : [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]
Vertex Cover approx (2-approx) : {0, 2} (taille 2)
TSP 2-opt (8 villes) :
Tournée : 0 → 4 → 7 → 5 → 1 → 2 → 3 → 6 → 0
Coût : 320
Heuristiques et métaheuristiques#
Remarque 48
Recuit simulé (simulated annealing). Inspiré du processus physique de recuit des métaux, le recuit simulé explore l’espace des solutions en acceptant parfois des solutions moins bonnes, avec une probabilité décroissant au fil du temps (la « température »). Cela permet d’échapper aux optima locaux.
Algorithmes génétiques. Inspirés de l’évolution darwinienne, ils maintiennent une population de solutions candidates et les font évoluer par sélection, croisement et mutation. Ils sont efficaces sur de nombreux problèmes d’optimisation combinatoire.
Algorithmes de colonies de fourmis, essaims de particules. D’autres métaheuristiques bio-inspirées, efficaces sur des instances pratiques même sans garantie de performance.
import math
def recuit_simule_tsp(distances, n, T_init=1000, T_fin=0.01, alpha=0.995, n_iter=5000):
"""
Recuit simulé pour le TSP.
Explore l'espace des tournées en acceptant des dégradations avec probabilité exp(-Δ/T).
"""
random.seed(0)
def cout(tournee):
return sum(distances[tournee[i]][tournee[(i+1) % n]] for i in range(n))
# Tournée initiale aléatoire
tournee = list(range(n))
random.shuffle(tournee)
meilleur_cout = cout(tournee)
meilleure_tournee = tournee[:]
T = T_init
historique = [meilleur_cout]
for _ in range(n_iter):
# Perturbation : échange de deux villes (2-opt swap)
i, j = sorted(random.sample(range(n), 2))
nouvelle_tournee = tournee[:i] + list(reversed(tournee[i:j+1])) + tournee[j+1:]
delta = cout(nouvelle_tournee) - cout(tournee)
if delta < 0 or random.random() < math.exp(-delta / T):
tournee = nouvelle_tournee
c = cout(tournee)
if c < meilleur_cout:
meilleur_cout = c
meilleure_tournee = tournee[:]
T = max(T * alpha, T_fin)
historique.append(meilleur_cout)
return meilleure_tournee, meilleur_cout, historique
if n_villes <= 10:
tournee_rs, cout_rs, hist = recuit_simule_tsp(distances, n_villes)
print(f"Recuit simulé ({n_villes} villes) :")
print(f" Meilleure tournée : {tournee_rs}")
print(f" Meilleur coût : {cout_rs}")
print(f" 2-opt coût : {cout}")
Recuit simulé (8 villes) :
Meilleure tournée : [1, 2, 3, 6, 0, 4, 7, 5]
Meilleur coût : 320
2-opt coût : 320
PSPACE et EXPTIME#
Au-delà de NP, la hiérarchie de complexité continue :
Remarque 49
PSPACE est la classe des problèmes solubles avec une quantité polynomiale de mémoire (indépendamment du temps). On a P ⊆ NP ⊆ PSPACE. Des problèmes PSPACE-complets incluent : l’évaluation des jeux à deux joueurs à information parfaite (échecs généralisés, go généralisé), la quantified boolean formula (QBF).
EXPTIME est la classe des problèmes solubles en temps exponentiel O(2^{p(n)}). On a PSPACE ⊆ EXPTIME. Des problèmes EXPTIME-complets sont liés à des jeux comme les échecs et le go sur des plateaux de taille générale.
On a la hiérarchie : P ⊆ NP ⊆ co-NP ⊆ PSPACE ⊆ EXPTIME, et toutes ces inclusions sont supposées strictes (mais seul P ⊊ EXPTIME est prouvé).
Cas particuliers polynomiaux#
Même pour un problème NP-difficile, des restrictions sur la structure de l’entrée peuvent rendre le problème polynomial.
Exemple 14 (Cas polynomiaux de problèmes NP-complets)
Coloration de graphe k=2 : la 2-coloration (test de bipartitité) est dans P via un simple BFS/DFS.
TSP sur arbre : si le graphe est un arbre, on peut trouver le circuit hamiltonien optimal en temps linéaire.
Sac à dos avec petits poids : si tous les poids
w_isont des entiers bornés par un polynôme enn, la DP en O(nW) est pseudo-polynomiale (polynomiale en la valeur numérique, non en la taille binaire).2-SAT : la satisfaisabilité de formules avec exactement 2 littéraux par clause est dans P, soluble par des composantes fortement connexes en O(n+m).
Graphes planaires : la coloration de graphes planaires avec 4 couleurs est toujours possible (théorème des 4 couleurs), et la 3-coloration des graphes planaires reste NP-complète.
def deux_sat(n_vars, implications):
"""
Résolution de 2-SAT par Kosaraju (composantes fortement connexes).
implications : liste de (u, v) signifiant ¬u → v et ¬v → u (clause u ∨ v)
Variables : 0..n-1 (variable i), n..2n-1 (négation i)
"""
N = 2 * n_vars
def neg(x):
return x + n_vars if x < n_vars else x - n_vars
graph = [[] for _ in range(N)]
graph_rev = [[] for _ in range(N)]
for u, v in implications:
# Clause (u ∨ v) ≡ (¬u → v) ∧ (¬v → u)
graph[neg(u)].append(v)
graph[neg(v)].append(u)
graph_rev[v].append(neg(u))
graph_rev[u].append(neg(v))
# Kosaraju : ordre de fin de DFS sur le graphe original
visittes = [False] * N
ordre_fin = []
def dfs1(u):
stack = [(u, iter(graph[u]))]
visittes[u] = True
while stack:
v, it = stack[-1]
try:
w = next(it)
if not visittes[w]:
visittes[w] = True
stack.append((w, iter(graph[w])))
except StopIteration:
ordre_fin.append(v)
stack.pop()
for i in range(N):
if not visittes[i]:
dfs1(i)
# DFS sur le graphe transposé dans l'ordre inverse
composante = [-1] * N
comp_id = 0
def dfs2(u, cid):
stack = [u]
composante[u] = cid
while stack:
v = stack.pop()
for w in graph_rev[v]:
if composante[w] == -1:
composante[w] = cid
stack.append(w)
for u in reversed(ordre_fin):
if composante[u] == -1:
dfs2(u, comp_id)
comp_id += 1
# Vérification et assignation
assignation = {}
for i in range(n_vars):
if composante[i] == composante[neg(i)]:
return None # Non satisfaisable
assignation[i] = composante[i] > composante[neg(i)]
return assignation
# Instance 2-SAT : (x0 ∨ x1) ∧ (¬x0 ∨ x2) ∧ (¬x1 ∨ ¬x2)
# Encodage : variable i → i, ¬i → i + n_vars
n_vars = 3
# Clause (x0 ∨ x1) : u=0, v=1
# Clause (¬x0 ∨ x2) : u=3 (¬x0), v=2
# Clause (¬x1 ∨ ¬x2) : u=4 (¬x1), v=5 (¬x2)
clauses_2sat = [(0, 1), (3, 2), (4, 5)]
sol = deux_sat(n_vars, clauses_2sat)
print(f"2-SAT résultat : {sol}")
if sol:
print("Solution :")
for i, val in sol.items():
print(f" x{i} = {val}")
2-SAT résultat : {0: True, 1: False, 2: True}
Solution :
x0 = True
x1 = False
x2 = True
Résumé#
Dans ce chapitre, nous avons exploré les fondements de la théorie de la complexité des problèmes :
La classe P contient les problèmes solubles en temps polynomial — les problèmes tractables.
La classe NP contient les problèmes dont les solutions peuvent être vérifiées en temps polynomial. On a P ⊆ NP, et la question P = NP reste l’une des plus grandes énigmes ouvertes de l’informatique.
Un problème est NP-complet s’il est dans NP et que tout problème de NP se réduit polynomialement à lui. Le premier problème NP-complet, SAT, a été identifié par Cook et Levin en 1971.
Des centaines de problèmes pratiques — coloration de graphes, TSP, sac à dos 0/1, satisfaisabilité — sont NP-complets.
Face à un problème NP-difficile, les stratégies pratiques incluent les algorithmes d’approximation (garantie de performance), les heuristiques et métaheuristiques (recuit simulé, algorithmes génétiques), et l’exploitation de cas particuliers polynomiaux.
La hiérarchie P ⊆ NP ⊆ PSPACE ⊆ EXPTIME structure les problèmes par leur difficulté intrinsèque.
Dans le chapitre suivant, nous étudierons les algorithmes probabilistes et randomisés, qui utilisent l’aléatoire comme outil algorithmique pour contourner les pires cas et concevoir des structures de données efficaces.