NP est la classe de langages dotés de vérificateurs de temps polynomial
La classe NP, qui signifie « temps polynomial non déterministe », est un concept fondamental de la théorie de la complexité computationnelle, un sous-domaine de l'informatique théorique. Pour comprendre NP, il faut d’abord saisir la notion de problèmes de décision, qui sont des questions auxquelles on répond par oui ou par non. Dans ce contexte, un langage fait référence à un ensemble de chaînes sur un certain alphabet, où chaque chaîne code une instance d'un problème de décision.
Un langage (L) est dit dans NP s’il existe un vérificateur en temps polynomial pour (L). Un vérificateur est un algorithme déterministe (V) qui prend deux entrées : une instance (x) et un certificat (y). Le certificat (y) est également appelé « témoin » ou « preuve ». Le vérificateur (V) vérifie si le certificat (y) confirme que (x) appartient à la langue (L). Formellement, un langage (L) est dans NP s'il existe un algorithme polynomial (V) et un polynôme (p(n)) tel que pour chaque chaîne (x dans L), il existe une chaîne (y) avec ( |y| leq p(|x|)) et (V(x, y) = 1). Inversement, pour chaque chaîne (x notin L), il n'y a pas de chaîne (y) telle que (V(x, y) = 1).
Pour élucider ce concept, considérons le problème bien connu de la « satisfiabilité booléenne » (SAT). Le problème SAT demande s'il existe une attribution de valeurs de vérité aux variables dans une formule booléenne donnée de telle sorte que la formule soit vraie. Le problème SAT est en NP car, étant donné une formule booléenne ( phi ) et une affectation ( alpha ) de valeurs de vérité à ses variables, on peut vérifier en temps polynomial si ( alpha ) satisfait ( phi ). Ici, l'instance ( x ) est la formule booléenne ( phi ) et le certificat ( y ) est l'affectation ( alpha ). Le vérificateur ( V ) vérifie si ( alpha ) rend ( phi ) vrai, ce qui peut être fait en temps polynomial par rapport à la taille de ( phi ).
Un autre exemple illustratif est le problème du « chemin hamiltonien ». Ce problème demande s'il existe un chemin dans un graphe donné qui visite chaque sommet exactement une fois. Le problème du chemin hamiltonien est également dans NP car, étant donné un graphe ( G ) et une séquence de sommets ( P ), on peut vérifier en temps polynomial si ( P ) est un chemin hamiltonien dans ( G ). Dans ce cas, l'instance ( x ) est le graphe ( G ) et le certificat ( y ) est la séquence de sommets ( P ). Le vérificateur ( V ) vérifie si ( P ) forme un chemin hamiltonien, ce qui peut être effectué en temps polynomial par rapport à la taille de ( G ).
Le concept de vérifiabilité en temps polynomial est important car il fournit un moyen de caractériser des problèmes qui sont efficacement vérifiables, même si trouver la solution peut être impossible par calcul. Cela nous amène à la fameuse question de savoir si ( P = NP ), qui demande si tout problème dont la solution peut être vérifiée en temps polynomial peut également être résolu en temps polynomial. La classe ( P ) est constituée de problèmes de décision qui peuvent être résolus en temps polynomial par une machine de Turing déterministe. Si ( P = NP ), cela signifierait que chaque problème avec un vérificateur en temps polynomial a également un solveur en temps polynomial. Cette question reste l’un des problèmes ouverts les plus importants en informatique.
L’une des propriétés clés de NP est qu’il est fermé sous réductions en temps polynomial. Une réduction en temps polynomial d'un langage ( L_1 ) à un langage ( L_2 ) est une fonction calculable en temps polynomial ( f ) telle que ( x dans L_1 ) si et seulement si ( f(x) dans L_2 ). S'il existe une réduction du temps polynomial de ( L_1 ) à ( L_2 ) et que ( L_2 ) est dans NP, alors ( L_1 ) est également dans NP. Cette propriété joue un rôle déterminant dans l'étude de la complétude NP, qui identifie les problèmes « les plus difficiles » dans NP. Un problème est NP-complet s’il est dans NP et tout problème dans NP peut y être réduit en temps polynomial. Le problème SAT a été le premier problème prouvé NP-complet, et il sert de base pour prouver le NP-complétude d'autres problèmes.
Pour illustrer davantage le concept de vérifiabilité en temps polynomial, considérons le problème de la « somme de sous-ensembles ». Ce problème demande s'il existe un sous-ensemble d'un ensemble donné d'entiers dont la somme correspond à une valeur cible spécifiée. Le problème de la somme des sous-ensembles est en NP car, étant donné un ensemble d'entiers ( S ), une valeur cible ( t ) et un sous-ensemble ( S' ) de ( S ), on peut vérifier en temps polynomial si la somme des éléments dans ( S' ) est égal à ( t ). Ici, l'instance ( x ) est la paire ( (S, t) ) et le certificat ( y ) est le sous-ensemble ( S' ). Le vérificateur ( V ) vérifie si la somme des éléments dans ( S' ) est égale à ( t ), ce qui peut être fait en temps polynomial par rapport à la taille de ( S ).
L’importance de la vérifiabilité en temps polynomial s’étend au-delà des considérations théoriques. Concrètement, cela signifie que pour les problèmes NP, si une solution proposée (certificat) est fournie, elle peut être vérifiée efficacement. Cela a des implications significatives pour les protocoles cryptographiques, les problèmes d'optimisation et divers domaines où la vérification de l'exactitude d'une solution est importante.
Pour résumer, la classe NP englobe des problèmes de décision pour lesquels une solution proposée peut être vérifiée en temps polynomial par un algorithme déterministe. Ce concept est fondamental dans la théorie de la complexité informatique et a de profondes implications pour les aspects théoriques et pratiques de l’informatique. L'étude de NP, de la vérifiabilité en temps polynomial et de concepts connexes tels que la complétude NP continue d'être un domaine de recherche dynamique et critique.
D'autres questions et réponses récentes concernant Complexité:
- La classe PSPACE n'est-elle pas égale à la classe EXPSPACE ?
- La classe de complexité P est-elle un sous-ensemble de la classe PSPACE ?
- Pouvons-nous prouver que les classes Np et P sont identiques en trouvant une solution polynomiale efficace pour tout problème NP complet sur une MT déterministe ?
- La classe NP peut-elle être égale à la classe EXPTIME ?
- Existe-t-il des problèmes dans PSPACE pour lesquels il n’existe aucun algorithme NP connu ?
- Un problème SAT peut-il être un problème NP complet ?
- Un problème peut-il appartenir à la classe de complexité NP s'il existe une machine de Turing non déterministe qui le résoudra en temps polynomial
- P et NP sont-ils réellement la même classe de complexité ?
- Tous les langages sans contexte appartiennent-ils à la classe de complexité P ?
- Y a-t-il une contradiction entre la définition de NP comme une classe de problèmes de décision avec des vérificateurs en temps polynomial et le fait que les problèmes de la classe P ont également des vérificateurs en temps polynomial ?
Voir plus de questions et réponses dans Complexité