Classes P, NP, NP-complet, NP-difficile

🎯

Introduction : pourquoi classer les problèmes ?

En informatique, certains problèmes sont faciles à résoudre par un ordinateur, d'autres sont très difficiles, voire impossibles à résoudre rapidement même avec les meilleurs ordinateurs du monde.

Pour organiser cette idée, les informaticiens ont créé des classes de complexité : des familles de problèmes qui ont le même niveau de difficulté.

Imagine un jeu de puzzle. Assembler les pièces peut être très long. Mais vérifier qu'un puzzle est fini prend 2 secondes. C'est exactement l'idée derrière P et NP !

Sur cette page, on ne parle que de problèmes de décision : des problèmes dont la réponse est toujours OUI ou NON.

📄

Instance et Vérificateur

Avant de parler de P et NP, deux mots clés à retenir :

📌 Instance (d'un problème) Une instance est un exemple concret d'un problème général. C'est les données spécifiques que l'on donne à l'algorithme.

Exemple : Le problème général est « Ce graphe G contient-il un chemin hamiltonien ? »
Une instance serait : « Est-ce que ce graphe précis (5 sommets, ces arêtes) contient un chemin hamiltonien ? »

📌 Vérificateur Un vérificateur est un algorithme qui, à partir d'une instance et d'une solution candidate, répond OUI ou NON : la solution proposée est-elle correcte ?

Il ne cherche pas la solution lui-même, il vérifie seulement si la solution qu'on lui propose est valide, et le fait rapidement.

Le vérificateur, c'est le professeur qui corrige ta copie. Il ne refait pas l'exercice : il vérifie simplement si ta réponse est juste.

🔎 Exemple concret :

Problème : Ce tableau contient-il un sous-ensemble dont la somme vaut 0 ?
Instance : Tableau = [3, −2, 7, −5, 4, −3]
Solution candidate : {3, −2, −5, 4} → somme = 3 − 2 − 5 + 4 = 0
Vérificateur : Additionne les nombres et vérifie que la somme vaut 0. ✅ Simple et rapide !

Classe P – Les problèmes « faciles »

📌 Définition P est l'ensemble des problèmes de décision qui peuvent être résolus par un algorithme en temps polynomial (c'est-à-dire en O(n^k) opérations pour une certaine constante k).

Multiplier deux nombres à n chiffres : plus n est grand, plus c'est long, mais le temps reste raisonnable. C'est un problème dans P.

Temps polynomial = le temps de calcul ne s'emballe pas. Si la taille de l'entrée double, le temps augmente d'un facteur raisonnable (n², n³…), pas de manière explosive comme 2ⁿ.

✅ Exemples de problèmes dans P :

Trier une liste de n nombres (tri fusion : O(n log n))
Chercher un élément dans une liste
Savoir si un graphe est connexe
Savoir si un nombre est premier (algorithme AKS, 2002)
Plus court chemin dans un graphe (algorithme de Dijkstra)

P ⊆ NP : tout problème dans P est aussi dans NP, car si on peut résoudre rapidement, on peut aussi vérifier rapidement.

Classe NP – Facile à vérifier, difficile à résoudre ?

📌 Définition NP (Non-déterministe Polynomial) est l'ensemble des problèmes de décision pour lesquels une solution candidate peut être vérifiée en temps polynomial.

Trouver la solution peut être très long, mais vérifier qu'une solution est correcte est rapide.

Imagine un cadenas à code à 10 chiffres. Trouver le bon code par force brute est très long (10 milliards de combinaisons). Mais si quelqu'un te donne le code, tu le vérifies en 2 secondes !

✅ Exemples de problèmes dans NP :

Problème du voyageur de commerce (version décision) : existe-t-il un tour de longueur ≤ k passant par toutes les villes ? Vérifier un tour proposé est facile.
Problème de la clique : ce graphe contient-il un groupe de k sommets tous reliés entre eux ? Vérifier une clique proposée est facile.
SAT (satisfaisabilité booléenne) : cette formule logique peut-elle être rendue vraie ?
Problème du sac à dos : peut-on remplir ce sac avec des objets de valeur totale ≥ V ?

La grande question ouverte en informatique : P = NP ? Tout ce qu'on peut vérifier rapidement peut-il aussi être trouvé rapidement ? On ne sait pas encore ! C'est un problème du millénaire (récompense : 1 million de dollars).

NP-C

NP-complet – Les problèmes les plus durs de NP

📌 Définition Un problème est NP-complet s'il satisfait deux conditions :

Il est dans NP (une solution peut être vérifiée en temps polynomial).
Il est NP-difficile (tous les problèmes de NP se réduisent à lui en temps polynomial).

Imagine un problème universel, un roi des problèmes. Si tu trouves un algorithme rapide pour ce roi, tu en trouves automatiquement un pour tous les problèmes de NP. Les NP-complets sont ces rois.

Le premier problème prouvé NP-complet est SAT (satisfaisabilité booléenne), par Stephen Cook en 1971. Depuis, on en connaît des milliers.

✅ Exemples de problèmes NP-complets :

SAT (satisfaisabilité d'une formule booléenne)
3-SAT (SAT avec des clauses de 3 variables)
Problème de la clique
Coloration de graphe (avec k couleurs, k ≥ 3)
Circuit hamiltonien
Problème du sac à dos (version décision)

NP-complet ⊂ NP : tout problème NP-complet est aussi dans NP. Mais en plus, il est parmi les plus difficiles de NP.

NP-D

NP-difficile – Au moins aussi dur que NP-complet

📌 Définition Un problème est NP-difficile (ou NP-hard) si tous les problèmes de NP peuvent lui être réduits en temps polynomial.

Il n'est pas nécessairement dans NP lui-même : la solution n'est pas forcément vérifiable rapidement.

C'est un problème encore plus exigeant que les rois : au moins aussi difficile que tout problème NP-complet, mais pas forcément un problème de décision avec vérification rapide.

Difference NP-complet vs NP-difficile :

NP-complet = dans NP ET NP-difficile. On peut vérifier une solution rapidement.
NP-difficile = NP-difficile mais pas forcément dans NP. La verification peut aussi etre difficile.

✅ Exemples de problèmes NP-difficiles hors NP-complets :

Problème de l'arrêt (Halting Problem) — pas du tout décidable !
Version optimisation du problème du voyageur de commerce (trouver le tour le plus court, sans borne fixée)
Jeu d'echecs generalisé (position gagnante en k coups)

Tout problème NP-complet est NP-difficile. Mais tout problème NP-difficile n'est pas NP-complet (il peut être encore plus dur, ou hors de NP).

≤ₚ

Réduction polynomiale – A se réduit à B

📌 Définition On dit que le problème A se réduit polynomialement à B (noté A ≤_P B) s'il existe une fonction f, calculable en temps polynomial, qui transforme toute instance de A en instance de B, telle que :

x est une instance OUI de A si et seulement si f(x) est une instance OUI de B.

Problème A
instance x

→
f(x) en temps polynomial

Problème B
instance f(x)

Imagine que tu sais deja resoudre B. La reduction te dit : pour resoudre A, il suffit de traduire ton probleme A en probleme B, puis d'utiliser le solveur de B. Si B est facile et que la traduction est rapide, alors A est aussi facile.

Ce que cela implique : Si A ≤_P B, alors B est au moins aussi difficile que A. Savoir resoudre B suffit a resoudre A.

🔎 Exemple :

3-SAT se réduit au problème de la Clique.
Cela signifie : si tu sais resoudre Clique rapidement, tu sais aussi resoudre 3-SAT rapidement.
Donc Clique est au moins aussi difficile que 3-SAT.

📌 Pourquoi les réductions sont importantes ?

Elles permettent de prouver qu'un problème est NP-complet.
Methode : on prend un NP-complet connu (ex : SAT), on le reduit au nouveau probleme. Donc le nouveau probleme est aussi NP-complet.
La relation ≤_P est transitive : si A ≤_P B et B ≤_P C, alors A ≤_P C.

📊 Diagramme des classes de complexité

Représentation dans le cas supposé P ≠ NP

📋 Tableau récapitulatif des classes

Classe	Résolution rapide ?	Vérification rapide ?	Dans NP ?	Exemple
P	✅ Oui	✅ Oui	✅ Oui	Tri, recherche
NP	❓ Peut-etre non	✅ Oui	✅ Oui	SAT, Clique
NP-complet	❓ Inconnu (probablement non)	✅ Oui	✅ Oui	SAT, Hamiltonien
NP-difficile	❌ Probablement non	❌ Pas necessairement	❌ Pas necessairement	Probleme de l'arret

🔒 Complexité algorithmique