Algorithmique · Écoles d'ingénieurs — ENSIAS

Introduction à la théorie de la complexité (P vs NP)

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

La théorie de la complexité classe les problèmes selon les ressources nécessaires pour les résoudre.

Classe P : Ensemble des problèmes de décision résolubles en temps polynomial $O(n^k)$ . Ils sont considérés comme "faciles" ou "tractables".
Classe NP : Ensemble des problèmes dont une solution proposée peut être vérifiée en temps polynomial.
Relation P $\subseteq$ NP : Tout problème dans P est dans NP. La question ouverte est de savoir si P = NP.
NP-complétude : Un problème $L$ est NP-complet s'il est dans NP et si tout problème de NP peut être réduit à $L$ en temps polynomial.

Méthodes à maîtriser

Vérification d'un certificat : Savoir démontrer qu'un problème appartient à NP en montrant qu'une solution donnée se vérifie en $O(n^k)$ .
Réduction polynomiale : Utiliser une transformation $f$ telle que $x \in A \iff f(x) \in B$ pour prouver la difficulté relative.
Analyse de complexité : Identifier si un algorithme est de type exponentiel $O(2^n)$ ou polynomial $O(n^k)$ .

Exemples corrigés

Exemple 1 : Le tri par insertion est dans P car sa complexité est $O(n^2)$ .
Exemple 2 : Le problème du voyageur de commerce (TSP) est dans NP car, étant donné un circuit, on peut sommer les poids des arêtes en $O(n)$ et vérifier s'ils sont inférieurs à $K$ .

Erreurs fréquentes

Confondre "NP" avec "Non-Polynomial" (NP signifie Nondeterministic Polynomial).
Croire que P = NP est démontré (c'est l'un des problèmes du millénaire non résolu).
Penser qu'un problème NP-complet est impossible à résoudre (on peut trouver des solutions approchées ou heuristiques).

L'essentiel du cours

La théorie de la complexité classe les problèmes selon les ressources nécessaires pour les résoudre.

Classe P : Ensemble des problèmes de décision résolubles en temps polynomial $O(n^k)$. Ils sont considérés comme "faciles" ou "tractables".
Classe NP : Ensemble des problèmes dont une solution proposée peut être vérifiée en temps polynomial.
Relation P $\subseteq$ NP : Tout problème dans P est dans NP. La question ouverte est de savoir si P = NP.
NP-complétude : Un problème $L$ est NP-complet s'il est dans NP et si tout problème de NP peut être réduit à $L$ en temps polynomial.

Méthodes à maîtriser

Vérification d'un certificat : Savoir démontrer qu'un problème appartient à NP en montrant qu'une solution donnée se vérifie en $O(n^k)$.
Réduction polynomiale : Utiliser une transformation $f$ telle que $x \in A \iff f(x) \in B$ pour prouver la difficulté relative.
Analyse de complexité : Identifier si un algorithme est de type exponentiel $O(2^n)$ ou polynomial $O(n^k)$.

Exemples corrigés

Exemple 1 : Le tri par insertion est dans P car sa complexité est $O(n^2)$.
Exemple 2 : Le problème du voyageur de commerce (TSP) est dans NP car, étant donné un circuit, on peut sommer les poids des arêtes en $O(n)$ et vérifier s'ils sont inférieurs à $K$.

Erreurs fréquentes

Confondre "NP" avec "Non-Polynomial" (NP signifie Nondeterministic Polynomial).
Croire que P = NP est démontré (c'est l'un des problèmes du millénaire non résolu).
Penser qu'un problème NP-complet est impossible à résoudre (on peut trouver des solutions approchées ou heuristiques).

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Introduction à la théorie de la complexité (P vs NP)

1/4

La classe P est définie par :

❓ Questions fréquentes

Est-ce que la programmation dynamique aide à résoudre NP ?

Elle permet de résoudre certains problèmes NP-complets en temps pseudo-polynomial (ex: sac à dos), mais elle reste exponentielle par rapport à la taille de l'entrée (ex: valeur des objets).

💡 À retenir : La programmation dynamique optimise, mais ne transforme pas un problème NP-complet en P.

Qu'est-ce qu'un problème de décision ?

C'est un problème dont la réponse est binaire : "Oui" ou "Non".
Par exemple : "Existe-t-il un chemin de longueur inférieure à $K$ ?" est un problème de décision.
À l'inverse, "Quel est le plus court chemin ?" est un problème d'optimisation.

💡 À retenir : La théorie de la complexité se concentre sur les problèmes de décision pour simplifier l'analyse mathématique.

C'est un problème dont la réponse est binaire : "Oui" ou "Non".
Par exemple : "Existe-t-il un chemin de longueur inférieure à $K$ ?" est un problème de décision.
À l'inverse, "Quel est le plus court chemin ?" est un problème d'optimisation.

💡 À retenir : La théorie de la complexité se concentre sur les problèmes de décision pour simplifier l'analyse mathématique.

Chno hiya lfar9 bin P w NP?

P (Polynomial) : Lmasail li 3ndna khwarizmiya kat7elhom f wa9t mnasb (b7al l'ordre dyal $n^2$ ).
NP (Nondeterministic Polynomial) : Lmasail li ila 3tawni l7al, n9der nvéryih wach s7i7 f wa9t mnasb.
Lfar9 howa l'efficacité : P = "sahl t7el", NP = "sahl tvéryi".

💡 À retenir : P est l'ensemble des problèmes "faciles à résoudre", NP est l'ensemble des problèmes "faciles à vérifier".

P (Polynomial) : Lmasail li 3ndna khwarizmiya kat7elhom f wa9t mnasb (b7al l'ordre dyal $n^2$).
NP (Nondeterministic Polynomial) : Lmasail li ila 3tawni l7al, n9der nvéryih wach s7i7 f wa9t mnasb.
Lfar9 howa l'efficacité : P = "sahl t7el", NP = "sahl tvéryi".

💡 À retenir : P est l'ensemble des problèmes "faciles à résoudre", NP est l'ensemble des problèmes "faciles à vérifier".

Est-ce que tous les problèmes NP sont difficiles ?

Non. Comme P $\subseteq$ NP, tous les problèmes de la classe P sont aussi dans NP. Or, les problèmes de P sont faciles. Ce sont les problèmes "NP-complets" qui sont considérés comme les plus difficiles de la classe NP.

💡 À retenir : NP contient à la fois des problèmes faciles (P) et des problèmes très complexes (NP-complets).

Kifach n3ref wach chi mochkil NP-complet?

Khass lmochkil ykon f NP (n9dro nvéryiw l7al).
Khass ay mochkil akhor f NP ykon momkin nredoh (réduction) lhad lmochkil.
Ila 7liti had lmochkil, rak 7liti ga3 lmasail f NP.

💡 À retenir : La réduction est l'outil clé pour prouver la NP-complétude.

Pourquoi P vs NP est-il si important ?

Si P = NP, cela signifierait que tout problème dont la solution est facile à vérifier est aussi facile à résoudre. Cela révolutionnerait la cryptographie, l'optimisation et l'intelligence artificielle.

💡 À retenir : C'est le problème ouvert le plus célèbre en informatique théorique.

Est-ce qu'un algorithme exponentiel est toujours dans NP ?

Oui, s'il s'agit d'un problème de décision. La classe NP définit la complexité de la vérification, pas celle de la résolution. Un problème peut être très long à résoudre (exponentiel) mais très rapide à vérifier (polynomial).

💡 À retenir : NP ne limite pas le temps de résolution, seulement le temps de vérification.

Wach l'algo glouton (greedy) kay7el ga3 lmasail NP?

La, l'algo glouton kay3ti 7al srii3 walakin machi dima l7al l'amthal (optimal). F lmasail NP-complets, l'algo glouton kay3ti ghir "approximation".

💡 À retenir : Les algorithmes gloutons sont des heuristiques pour les problèmes difficiles.

Qu'est-ce qu'un certificat ?

C'est une preuve ou une donnée supplémentaire qui permet de vérifier rapidement si une instance d'un problème a une réponse "Oui". Par exemple, pour le problème du cycle hamiltonien, le certificat est la liste des sommets du cycle.

💡 À retenir : Sans certificat, la vérification ne serait pas polynomiale.

Un problème peut-il être plus dur que NP ?

Oui, il existe des problèmes "NP-difficiles" (NP-hard) qui ne sont pas forcément dans NP, et des problèmes indécidables (comme le problème de l'arrêt) qui ne peuvent être résolus par aucun algorithme.

💡 À retenir : NP est une sous-classe de problèmes complexes, mais il existe des problèmes encore plus inaccessibles.

Comment prouver qu'un problème est dans P ?

Il suffit de concevoir un algorithme qui résout le problème et de démontrer que sa complexité temporelle est bornée par une fonction polynomiale $O(n^k)$ .

💡 À retenir : La construction d'un algorithme polynomial est la preuve directe de l'appartenance à P.

Il suffit de concevoir un algorithme qui résout le problème et de démontrer que sa complexité temporelle est bornée par une fonction polynomiale $O(n^k)$.

💡 À retenir : La construction d'un algorithme polynomial est la preuve directe de l'appartenance à P.

Quelle est la différence entre une réduction et un algorithme ?

Une réduction transforme une instance d'un problème A en une instance d'un problème B. Un algorithme résout directement le problème. La réduction sert à comparer la difficulté entre deux problèmes.

💡 À retenir : Réduire A à B signifie que B est au moins aussi difficile que A.

✍️ Exercices type examen national

Exercice 1

Soit le problème de la "Somme de sous-ensemble" (Subset Sum) : Étant donné un ensemble d'entiers $S$ et un entier $K$ , existe-t-il un sous-ensemble de $S$ dont la somme est égale à $K$ ?

Montrer que ce problème appartient à la classe NP.
Expliquer pourquoi une recherche exhaustive (tester tous les sous-ensembles) n'est pas une solution polynomiale.

Exercice 1

Soit le problème de la "Somme de sous-ensemble" (Subset Sum) : Étant donné un ensemble d'entiers $S$ et un entier $K$, existe-t-il un sous-ensemble de $S$ dont la somme est égale à $K$ ?

Montrer que ce problème appartient à la classe NP.
Expliquer pourquoi une recherche exhaustive (tester tous les sous-ensembles) n'est pas une solution polynomiale.

Voir la correction détaillée : inscription gratuite

Exercice 2

On considère un algorithme $A$ qui résout un problème en $O(n^3)$ et un algorithme $B$ qui résout un autre problème en $O(2^n)$ .

Lequel appartient à la classe P ? Justifiez.
Si $n=50$ , comparez le nombre d'opérations.

Exercice 2

On considère un algorithme $A$ qui résout un problème en $O(n^3)$ et un algorithme $B$ qui résout un autre problème en $O(2^n)$.

Lequel appartient à la classe P ? Justifiez.
Si $n=50$, comparez le nombre d'opérations.

Voir la correction détaillée : inscription gratuite

Exercice 3

Expliquez le concept de réduction polynomiale entre deux problèmes $A$ et $B$ ( $A \leq_p B$ ).

Exercice 3

Expliquez le concept de réduction polynomiale entre deux problèmes $A$ et $B$ ($A \leq_p B$).

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Algorithmique

Introduction à l'algorithmique et complexité Structures de données linéaires : Listes, Piles et Files Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Arbres binaires et arbres de recherche Structures de données avancées : Tas (Heaps) et Files de priorité Tables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Algorithmes sur les graphes : Plus courts chemins et arbres couvrants Programmation dynamique Algorithmes gloutons