backend / algorithmes-structures-donnees
NP-complétude et réductions
Explication
Ce que vous allez apprendre
- Distinguer la difficulté de VÉRIFIER une solution de celle de la TROUVER depuis zéro
- Définir la classe NP à partir de la vérifiabilité en temps polynomial
- Expliquer ce qu'est une réduction et pourquoi elle relie les problèmes NP-complets entre eux
- Formuler la question ouverte P = NP et ses implications pratiques
- Réagir de façon appropriée face à un problème reconnu NP-complet, en production comme en entretien technique
Dans quel contexte ?
Un ingénieur logistique doit calculer l'itinéraire optimal d'un livreur passant par 50 adresses dans la journée, en minimisant la distance totale parcourue (le problème du voyageur de commerce). Après plusieurs jours à chercher un algorithme rapide et exact, il découvre que ce problème est NP-complet : aucun algorithme connu ne le résout en temps polynomial pour un grand nombre d'adresses. Reconnaître cette classification change l'approche : au lieu de chercher un "code parfait", l'ingénieur adopte une heuristique (comme l'algorithme du plus proche voisin) qui donne une bonne solution approchée en temps raisonnable, plutôt que la solution exacte inaccessible.
D'abord, une question qui n'a rien d'évident
Après avoir vu de nombreux algorithmes efficaces, il est temps de se demander : existe-t-il des problèmes pour lesquels AUCUN algorithme rapide n'est connu, malgré des décennies de recherche ?
Prérequis
Cette leçon suppose familier le problème du sac à dos (leçon 18) et le backtracking (leçon 20), deux exemples typiques de problèmes NP-difficiles abordés par approximation ou recherche exhaustive élaguée.
L'angle choisi pour répondre à cette question
La théorie de la complexité classe les problèmes selon une distinction essentielle : la difficulté à VÉRIFIER une solution proposée, par opposition à la difficulté à la TROUVER depuis zéro.
Étape 1 : la classe NP
Un problème appartient à NP si, étant donné une solution candidate, on peut vérifier en temps raisonnable si elle est correcte — même si la trouver depuis zéro peut demander d'explorer un nombre exponentiel de possibilités.
Un exemple concret de cette asymétrie
Vérifier qu'un sous-ensemble de nombres donné somme bien à une valeur cible est instantané. Mais trouver ce sous-ensemble parmi toutes les combinaisons possibles peut demander d'en tester un nombre exponentiel.
| Classe | Vérifier une solution | Trouver une solution | Exemple |
|---|---|---|---|
| P | Rapide (polynomial) | Rapide (polynomial) | Tri, plus court chemin (Dijkstra) |
| NP | Rapide (polynomial) | Aucun algorithme rapide connu en général | Voyageur de commerce, sac à dos |
| NP-complet | Rapide (polynomial) | Aucun algorithme rapide connu, et tout NP s'y ramène | SAT, coloration de graphe |
Étape 2 : les problèmes NP-complets
Certains problèmes NP sont si centraux que tous les autres problèmes de NP peuvent s'y ramener : ce sont les problèmes NP-complets.
Le mécanisme qui prouve ce lien
Une "réduction" transforme une instance d'un problème A en une instance d'un problème B, de façon à ce que résoudre B revienne à résoudre A.
Astuce
Reconnaître qu'un problème est NP-complet est déjà une information précieuse en entretien ou en production : cela justifie de proposer une heuristique, une approximation, ou une résolution exacte limitée à de petites tailles, plutôt que de chercher indéfiniment un algorithme exact rapide qui n'existe probablement pas.
La conséquence vertigineuse de ces réductions
Si un seul problème NP-complet trouvait un jour un algorithme rapide, tous les autres en bénéficieraient instantanément — c'est précisément la question ouverte "P = NP ?", l'un des plus grands problèmes non résolus de l'informatique.
Ce qu'il faut retenir en pratique
Reconnaître qu'un problème est NP-complet n'est pas un aveu d'échec, mais une information précieuse : on se tourne alors vers des heuristiques, des approximations, ou des solveurs spécialisés efficaces sur des instances de taille raisonnable.
Vers la suite
Cette théorie décrit ce que fait un algorithme déterministe. La toute dernière leçon de ce cours montre, à l'inverse, comment introduire volontairement du hasard peut rendre un algorithme plus fiable plutôt que moins.
Commandes & code
NP-complétude et réductions
NP : une solution proposée (certificat) se VÉRIFIE en temps polynomial, même si la TROUVER peut être exponentielle.
from itertools import combinations
# --- Subset Sum : NP-complet, illustre vérification rapide vs recherche exponentielle ---
def verifier_certificat_subset_sum(nombres: list[int], cible: int, sous_ensemble: list[int]) -> bool:
# Vérification en O(n) : ce sous-ensemble précis somme-t-il bien à la cible ?
restants = list(nombres)
for x in sous_ensemble:
if x not in restants:
return False
restants.remove(x)
return sum(sous_ensemble) == cible
def resoudre_subset_sum_force_brute(nombres: list[int], cible: int) -> list[int] | None:
# Résolution : O(2^n) dans le pire cas -- explore TOUS les sous-ensembles possibles
n = len(nombres)
for taille in range(n + 1):
for combo in combinations(nombres, taille):
if sum(combo) == cible:
return list(combo)
return None
nombres = [3, 34, 4, 12, 5, 2]
solution = resoudre_subset_sum_force_brute(nombres, 9)
assert solution is not None
assert verifier_certificat_subset_sum(nombres, 9, solution) # vérification triviale et rapide
# --- Réduction polynomiale : Partition se réduit à Subset Sum ---
# Partition : peut-on diviser un ensemble en deux parties de SOMME ÉGALE ?
# Réduction : Partition(nombres) est un OUI <=> SubsetSum(nombres, sum(nombres) / 2) est un OUI
# Si Subset Sum était résoluble en temps polynomial, Partition le serait aussi via cette réduction
def partition_via_subset_sum(nombres: list[int]) -> tuple[list[int], list[int]] | None:
total = sum(nombres)
if total % 2 != 0:
return None # somme impaire : partition égale impossible, inutile de chercher
moitie = resoudre_subset_sum_force_brute(nombres, total // 2)
if moitie is None:
return None
reste = list(nombres)
for x in moitie:
reste.remove(x)
return moitie, reste
resultat = partition_via_subset_sum([1, 5, 11, 5])
assert resultat is not None
groupe_a, groupe_b = resultat
assert sum(groupe_a) == sum(groupe_b) == 11
# --- Réduction Vertex Cover <-> Independent Set (relation classique en théorie de la complexité) ---
# Un ensemble S est une couverture de sommets (vertex cover) d'un graphe G
# <=> le complémentaire V - S est un ensemble indépendant (independent set) de G
def couverture_vers_ensemble_independant(sommets: set, couverture: set) -> set:
return sommets - couverture # réduction triviale en O(n), une fois la théorie établie
sommets = {1, 2, 3, 4, 5}
couverture_valide = {2, 4} # supposée trouvée par un autre algorithme (exacte ou approchée)
ensemble_independant = couverture_vers_ensemble_independant(sommets, couverture_valide)
assert ensemble_independant == {1, 3, 5}
# Conséquence pratique : Vertex Cover, Subset Sum, SAT... sont NP-complets et se réduisent les uns
# aux autres -- aucun algorithme polynomial connu ne les résout tous (P = NP reste une question ouverte).
# En pratique : heuristiques, algorithmes d'approximation, programmation dynamique sur cas restreints,
# ou solveurs SAT/ILP optimisés pour des instances de taille raisonnable.Résumé
- NP = problèmes dont une solution proposée se vérifie en temps polynomial ; NP-complet = parmi les plus difficiles de NP, tous équivalents entre eux par réduction.
- Une réduction polynomiale de A vers B montre que résoudre B efficacement permettrait de résoudre A efficacement.
- Prouver qu'un nouveau problème est NP-complet se fait en le réduisant depuis un problème déjà connu NP-complet (Subset Sum, SAT, Vertex Cover, ...).
- En pratique face à un problème NP-complet : heuristique, approximation, restriction à des cas particuliers polynomiaux, ou solveur générique optimisé.
Exercices pratiques
Mission : convaincre le management d'arrêter de chercher un algorithme exact rapide
Objectif : Distinguer vérification et résolution sur un cas concret, et argumenter le choix d'une heuristique face à un problème NP-complet.
Contexte
Un ingénieur logistique cherche depuis trois semaines un algorithme "rapide et exact" pour planifier la tournée optimale d'un livreur passant par 60 adresses (le problème du voyageur de commerce). Son manager s'impatiente et demande "pourquoi ça prend autant de temps, c'est juste un problème de trajet". Tu dois lui expliquer la situation avec les outils de cette leçon.