Détails: Création : 26 mars 2025; Mis à jour : 27 mars 2025

Vote utilisateur: 5 / 5

Les problèmes NP-complets

Pourquoi certains problèmes semblent-ils faciles à vérifier, mais incroyablement difficiles à résoudre ?
Pourquoi les ordinateurs les plus puissants du monde échouent-ils encore à planifier un trajet optimal entre plusieurs villes, ou à résoudre certains casse-têtes logiques en un temps raisonnable ?

Ces questions, simples en apparence, sont au cœur d’un mystère profond de l’informatique théorique : le problème P = NP ?

Formulée pour la première fois dans les années 1970, cette énigme a donné naissance à une nouvelle branche des sciences informatiques

— la théorie de la complexité
— et à un concept central : la NP-complétude.

Dans cet article, nous vous proposons de remonter aux origines historiques de cette notion, de découvrir les premières intuitions des chercheurs, et de suivre l’évolution d’une idée qui continue de défier les mathématiciens, informaticiens et cryptographes du monde entier.

Plan :

I. Qu’est-ce qu’un problème NP-complet ?
- Notions de Bases
- Notion de temps polynomial
II. Histoire : P = NP ?
III. Des Exemples de problèmes P, NP, NP Complets et NP-Hard

I. Qu’est-ce qu’un problème NP-complet ?

🔹1. Quelques notions de base

Problème de décision : Un problème dont la réponse est "oui" ou "non".
- Exemple : Peut-on colorier ce graphe avec 3 couleurs sans que deux sommets adjacents aient la même couleur ?
Classe P : Ensemble des problèmes de décision qui peuvent être résolus efficacement par un algorithme déterministe en temps polynomial.
- Si un problème est dans P, alors il est "facile" à résoudre (par un ordinateur).
Classe NP : Ensemble des problèmes de décision dont une solution peut être vérifiée rapidement (en temps polynomial), même si on ne sait pas forcément comment la trouver rapidement.
- Si un problème est dans NP, il n’est pas forcément "facile" à résoudre, mais "facile" à vérifier.

Le temps polynomial est une notion centrale dans la compréhension des problèmes NP-complets et plus généralement de la complexité algorithmique.

🔹2. Qu’est-ce que le temps polynomial ?

Un algorithme s’exécute en temps polynomial si son temps d’exécution (c’est-à-dire le nombre d’opérations qu’il effectue) peut être borné par un polynôme en la taille de l’entrée.

2.1. Exemple de fonction polynomiale :

$f(n)= n$
$f(n)= n^2$
$f(n)=n^3 + 2n^2 + 7$

Ici, nn représente la taille de l’entrée (nombre d’éléments, nombre de sommets dans un graphe, longueur d’une chaîne, etc.)

2.2. Pourquoi c’est important ?

Quand on dit qu’un problème peut être résolu en temps polynomial, on veut dire que le temps de calcul grandit "raisonnablement" avec la taille du problème. C’est ce que l’on considère comme traitable en pratique, ou "efficace".

2.3. À l’inverse : le temps exponentiel

Un algorithme qui met un temps exponentiel à s’exécuter, comme :

$f(n)= 2^n$
$f(n)= n!$

devient très rapidement inutilisable dès que la taille du problème augmente un peu.

👉 Par exemple :

Si $n=50$ , alors $2^n \approx 1 \, 000 \, 000 \, 000 \, 000 =10^{12}$
Alors qu’avec $n^2$ , on n’a que 2 500

2.4. Application à NP et NP-complet

Un problème est dans P s’il peut être résolu en temps polynomial.
Un problème est dans NP s’il peut être vérifié en temps polynomial.
Un problème NP-complet est un problème dans NP, aussi dur que tous les autres de NP, et on ne connaît aucun algorithme en temps polynomial pour le résoudre… mais on ne sait pas non plus s’il en existe un.

2.5. Attention

Dire qu’un problème est résolu en temps polynomial ne signifie pas forcément que l’algorithme est rapide dans l’absolu !

Par exemple :

Un algorithme en $n^{10}$ est polynomial, mais peut être lent en pratique pour de grandes valeurs de n.

C’est pourquoi on distingue aussi la complexité théorique (P vs NP) de l’efficacité pratique (temps réel, mémoire, constantes).

2.6. En résumé

Le temps polynomial désigne une croissance du temps de calcul qui reste "gérable" à mesure que le problème grandit.
C’est le critère mathématique retenu pour définir si un algorithme est efficace ou réaliste du point de vue de la théorie de la complexité.

🔹3. Le lien entre P et NP

Tout problème dans P est aussi dans NP, car si on peut résoudre rapidement un problème, on peut aussi vérifier rapidement une solution.
Mais la grande question est :
P = NP ?
Personne ne le sait encore. C’est un des plus grands mystères de l’informatique théorique.

🔹4. Définition des problèmes NP-complets

Un problème NP-complet est un problème de décision qui est à la fois :

Dans NP : On peut vérifier une solution rapidement.
NP-difficile : Si on savait résoudre ce problème rapidement, on pourrait résoudre tous les problèmes de NP rapidement.

👉 Donc, résoudre un seul problème NP-complet en temps polynomial permettrait de résoudre tous les problèmes NP en temps polynomial. D’où leur importance !

Schéma 1 : Hiérarchie des classes de complexité

Voici une représentation simplifiée :

Diagram of intersection among classes P NP NP complete and NP hard problems 1

Dans cette image :

La classe P est incluse dans NP.
Les problèmes NP-complets sont au cœur de NP, mais aussi les plus difficiles.
Les NP-difficiles ne sont pas nécessairement dans NP (ils peuvent être plus durs).

II. Histoire : P = NP ?

Aux origines des problèmes NP-complets : une histoire de complexité

🔹 1971 : La naissance d’un problème fondamental

En 1971, Stephen Cook, chercheur à l’Université de Toronto, publie un article devenu légendaire :

The Complexity of Theorem-Proving Procedures

Ce texte, présenté lors d’un colloque en théorie de la complexité, pose pour la première fois une question qui va bouleverser l’informatique théorique :

Peut-on vérifier plus facilement une solution que la trouver ?

Dans cet article, Cook ne parle pas encore explicitement de problèmes "NP-complets", mais il y introduit le premier exemple d’un tel problème : SAT (le problème de satisfiabilité d'une formule logique booléenne). Il démontre que tout problème dont la solution peut être vérifiée rapidement (c’est-à-dire en temps polynomial) peut être réduit au problème SAT.

Ce résultat marque une étape fondatrice. Il établit ce que l’on appelle aujourd’hui le théorème de Cook, ou théorème de Cook-Levin, car Leonid Levin, en URSS, publie indépendamment la même découverte la même année, avec un autre exemple (un problème de pavage).

🔹 Une conférence animée et un débat ouvert

Lors de la conférence où Cook présente ses résultats, une vive discussion éclate parmi les chercheurs :

Les problèmes comme SAT peuvent-ils être résolus efficacement, c’est-à-dire en temps polynomial sur une machine de Turing déterministe ?

John Hopcroft, un informaticien influent, calme les débats en rappelant qu’aucune preuve définitive n’a été apportée, ni dans un sens, ni dans l’autre. Il convainc l’assemblée de remettre la question à plus tard — un plus tard qui dure encore aujourd’hui…

🔹 1972 : L’extension par Richard Karp

Un an plus tard, en 1972, un autre tournant historique a lieu. Richard Karp, professeur à Berkeley, publie un article fondamental intitulé :

Reducibility Among Combinatorial Problems

Dans ce texte, Karp démontre que 21 problèmes célèbres et très divers en informatique sont NP-complets. Parmi eux :

Le voyageur de commerce (TSP, version décision),
Le problème du sac à dos (Knapsack),
Le problème de couverture de sommets,
La coloration de graphe,
Etc.

Son travail montre que la NP-complétude ne concerne pas qu’un seul type de problème, mais un grand nombre de situations concrètes. Ces problèmes, bien que très différents en apparence, partagent une même structure de complexité.

🔹 NP-complet, qu’est-ce que ça signifie ?

Un problème est NP-complet s’il remplit deux conditions :

Il est dans NP : on peut vérifier une solution en temps polynomial.
Il est NP-difficile : tous les problèmes de NP peuvent être réduits à lui en temps polynomial.

Autrement dit, les problèmes NP-complets sont les plus durs parmi les problèmes pour lesquels une solution est facilement vérifiable.
👉 Si on trouve un algorithme rapide pour un seul problème NP-complet, on peut tous les résoudre rapidement !

🔹 La grande question : P = NP ?

La question centrale devient alors :

Les problèmes que l’on peut vérifier rapidement sont-ils aussi faciles à résoudre ?

Autrement dit, P = NP ?

Cette question est aujourd’hui l’un des sept "problèmes du prix du millénaire" proposés par l’Institut Clay.
La récompense : 1 million de dollars pour celui ou celle qui parviendra à démontrer que P = NP ou que P ≠ NP.

Pour résoudre ce mystère, il suffirait :

soit de trouver un algorithme rapide pour un problème NP-complet,
soit de prouver qu’un problème de NP ne peut pas être résolu rapidement, même en théorie.

Mais jusqu’à aujourd’hui, personne n’a réussi.

🔹 Et depuis ?

Depuis les années 1970 :

Des milliers de problèmes ont été classés comme NP-complets,
Les chercheurs ont développé des outils pour les reconnaître, les réduire entre eux, ou les approcher efficacement,
Des domaines entiers, comme la cryptographie, reposent sur l’hypothèse que P ≠ NP.

En pratique, même si ces problèmes sont "théoriquement durs", on peut souvent :

Les résoudre pour de petites instances,
Utiliser des algorithmes heuristiques ou probabilistes,
Trouver des solutions approximatives acceptables.

📌 En résumé

Élément clé	Détail
Date clé	1971 : publication de Cook
Personnalités	Cook, Levin, Hopcroft, Karp
Premier problème NP-complet	SAT
Débat ouvert	P = NP ?
Progrès depuis	Classification de milliers de problèmes
Problème du millénaire	Oui (1 million de dollars)

Bilan

Les problèmes NP-complets sont les plus importants et les plus étudiés dans la classe NP.
Personne ne sait si on peut les résoudre rapidement (P = NP ?).
Si on trouve un algorithme rapide pour un seul problème NP-complet, on résout tous les autres.
En pratique, on utilise souvent :
- Des algorithmes approximatifs
- Des méthodes heuristiques
- Ou on se contente de petites instances.

III. Des Exemples de problèmes P, NP, NP Complets et NP-Hard

hierarchie classes complexite

🟩 Classe P

Problèmes résolus efficacement (en temps polynomial).

Exemples :

Trier une liste d’entiers → (ex : tri rapide, tri fusion)
Trouver le plus court chemin dans un graphe pondéré avec poids positifs (ex : Dijkstra)
Recherche dans un tableau trié (ex : dichotomie)
Calcul de la plus grande valeur dans une liste
Multiplication de deux entiers

🟨 Classe NP

Problèmes dont on peut vérifier une solution rapidement, mais dont on ne connaît pas forcément d'algorithme efficace pour les résoudre.

Exemples :

Problème du sudoku : une solution (grille remplie) est facile à vérifier, mais longue à trouver
Trouver une combinaison de mots de passe correspondant à un hachage donné
Problème de Hamilton : un chemin qui passe une seule fois par chaque sommet ?

🟥 Classe NP-complet

Les problèmes les plus difficiles de NP.
S’ils sont résolus efficacement, tous les problèmes NP le sont aussi.

Définition :

Un problème est NP-complet s’il est :

Dans NP
NP-difficile (c’est-à-dire que tous les problèmes de NP peuvent se ramener à lui)

Exemples :

Problème SAT (satisfiabilité logique) : le tout premier problème prouvé NP-complet
Coloration de graphe (peut-on colorier un graphe avec 3 couleurs ?)
Problème du sac à dos (Knapsack), version décisionnelle
Voyageur de commerce (TSP), version "existe-t-il un trajet de coût ≤ k ?"
Problème du clique dans un graphe

🟧 Classe NP-difficile (NP-Hard)

Problèmes au moins aussi durs que les problèmes de NP, mais pas forcément vérifiables rapidement.

Définition :

Tous les problèmes de NP peuvent se ramener à ce problème, mais lui-même peut être en dehors de NP (pas de solution facilement vérifiable).

Exemples :

TSP (version optimisation) : quel est le plus court chemin pour visiter toutes les villes ?
Échecs (jeu complet) : gagner à partir d'une position donnée (problème PSPACE-complet)
Go ou Rubik's Cube (résolution optimale) : trouver la solution la plus rapide
Problèmes de planification d’horaires complexes (ex : emplois du temps avec contraintes)