La première chose à comprendre est que P et NP classent les langages, pas les problèmes. Pour comprendre ce que cela signifie, nous avons d’abord besoin d’autres définitions.
Un alphabet est un ensemble fini non vide de symboles.
{01} est un alphabet tout comme le jeu de caractères ASCII. {} n’est pas un alphabet car il est vide. N (les entiers) n’est pas un alphabet car il n’est pas fini.
Soit Σ un alphabet. Une concaténation ordonnée d’un nombre fini de symboles à partir de Σ est appelée un mot sur Σ.
La chaîne 101 est un mot sur l’alphabet { 01}. Le mot vide (souvent écrit ε) est un mot sur n’importe quel alphabet. La chaîne penguin est un mot sur l’alphabet contenant les caractères ASCII. La notation décimale du nombre π n’est pas un mot sur l’alphabet { .0123456789} car il n’est pas fini.
La longueur d’un mot w, écrit |w|, est le nombre de symboles qu’il contient.
Par exemple| /hello|/=5 et /ε/=0. Pour tout mot w, /w/∈ N et donc fini.
Soit Σ un alphabet. L’ensemble Σ＊ contient tous les mots sur Σ, y compris ε. L’ensemble Σ+ contient tous les mots sur Σ, à l’exclusion de ε. Pour n ∈ N, Σn est l’ensemble des mots de longueur n.
Pour chaque alphabet Σ, Σ＊ et Σ+ sont des ensembles dénombrables infinis. Pour le jeu de caractères ASCII ΣASCII, les expressions régulières .* et .+ désignent respectivement ΣASCII＊ et ΣASCII+.
{01}7 est l’ensemble des codes ASCII 7 bits { 00000000000001111111101} 32 est l’ensemble des valeurs entières de 32 bits.
Soit Σ un alphabet et L ⊆ Σ＊. L est appelé un langage sur Σ.
Pour un alphabet Σ, l’ensemble vide et Σ are sont des langages triviaux sur Σ. Le premier est souvent appelé la langue vide. La langue vide {} et la langue contenant uniquement le mot vide {ε} sont différentes.
Le sous-ensemble de {01}32 qui correspond à des valeurs à virgule flottante non NaN IEEE 754 est un langage fini.
Les langues peuvent avoir un nombre infini de mots mais chaque langue est dénombrable. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. L’ensemble infini de chaînes { 23571113,}} désignant les nombres premiers en notation décimale en est un sous-ensemble approprié. Le langage contenant tous les mots correspondant à l’expression régulière ?\d+\.\d*(?\d+)? est un langage sur le jeu de caractères ASCII (désignant un sous-ensemble des expressions valides à virgule flottante telles que définies par le langage de programmation C).
Il n’y a pas de langage contenant tous les nombres réels (dans n’importe quelle notation) car l’ensemble des nombres réels n’est pas dénombrable.
Soit Σ un alphabet et L ⊆ Σ＊. Une machine D décide L si pour chaque entrée w & in; Σ comp elle calcule la fonction caractéristique xL(w) en temps fini. La fonction caractéristique est définie comme
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.Une telle machine est appelée décideur pour L. Nous écrivons « D(w) =x » pour « donné w, D sorties x »”
Il existe de nombreux modèles de machines. Le plus général qui est utilisé aujourd’hui est le modèle d’une machine de Turing. Une machine de Turing dispose d’un stockage linéaire illimité regroupé en cellules. Chaque cellule peut contenir exactement un symbole d’un alphabet à tout moment. La machine de Turing effectue son calcul sous la forme d’une séquence d’étapes de calcul. À chaque étape, il peut lire une cellule, éventuellement écraser sa valeur et déplacer la tête de lecture / écriture d’une position vers la cellule gauche ou droite. L’action que la machine effectuera est contrôlée par un automate à états finis.
Une machine à accès aléatoire avec un ensemble fini d’instructions et un stockage illimité est un autre modèle de machine aussi puissant que le modèle de machine de Turing.
Pour les besoins de cette discussion, nous ne nous gênerons pas avec le modèle de machine précis que nous utilisons, mais il suffit de dire que la machine dispose d’une unité de contrôle déterministe finie, d’un stockage illimité et effectue un calcul sous la forme d’une séquence d’étapes pouvant être comptées.
Puisque vous l’avez utilisé dans votre question, je suppose que vous êtes déjà familier avec la notation ”big-O », alors voici seulement un rappel rapide.
Soit f:N → une fonction. L’ensemble O(f) contient toutes les fonctions g : N → N pour lesquelles il existe des constantes n0 ∈ N et c ∈ N telles que pour tout n ∈ N avec n > n0 il est vrai que g(n) ≤ c f(n).
Maintenant, nous sommes prêts à aborder la vraie question.
La classe P contient tous les langages L pour lesquels il existe une machine de Turing D qui décide L et une constante k ∈ N telle que pour chaque entrée w, D s’arrête après au plus T(|w/) étapes pour une fonction T ∈ O (n ↦ nk).
Puisque O(n ↦ nk), bien que mathématiquement correct, n’est pas pratique à écrire et à lire, la plupart des gens – pour être honnête, tout le monde sauf moi – écrivent généralement simplement O(nk).
Notez que la borne dépend de la longueur de w. Par conséquent, l’argument que vous faites pour le langage des nombres premiers n’est correct que pour les nombres dans les codages unaray, où pour le codage w d’un nombre n, la longueur du codage |w | est proportionnelle à n. Personne n’utiliserait jamais un tel codage en pratique. En utilisant un algorithme plus avancé que de simplement essayer tous les facteurs possibles, on peut cependant montrer que le langage des nombres premiers reste en P si les entrées sont codées en binaire (ou vers toute autre base). (Malgré un intérêt massif, cela n’a pu être prouvé que par Manindra Agrawal, Neeraj Kayal et Nitin Saxena dans un article primé en 2004, vous pouvez donc deviner que l’algorithme n’est pas très simple.)
Les langages triviaux {} et Σ＊ et le langage non trivial {ε} sont évidemment en P (pour tout alphabet Σ). Pouvez-vous écrire des fonctions dans votre langage de programmation préféré qui prennent une chaîne en entrée et renvoient un booléen indiquant si la chaîne est un mot du langage pour chacune d’entre elles et prouvent que votre fonction a une complexité d’exécution polynomiale?
Chaque langage régulier (un langage décrit par une expression régulière) est en P.
Soit Σ un alphabet et L &sous-ensemble eq; Σ＊. Une machine V qui prend un tuple codé de deux mots w, c ∈ Σ＊ et sort 0 ou 1 après un nombre fini d’étapes est un vérificateur pour L si elle a les propriétés suivantes.
- Étant donné (w, c), V ne produit 1 que si w ∈ L.
- Pour chaque w ∈ L, il existe un c ∈ Σ＊ tel que V(w, c) = 1.
Le c dans la définition ci-dessus est appelé témoin (ou certificat).
Un vérificateur est autorisé à donner de faux négatifs pour le mauvais témoin même si w est en fait dans L. Il n’est cependant pas autorisé à donner de faux positifs. Il est également nécessaire que pour chaque mot de la langue, il existe au moins un témoin.
Pour le langage COMPOSITE, qui contient les codages décimaux de tous les entiers qui ne sont pas premiers, un témoin pourrait être une factorisation. Par exemple, (659, 709) est un témoin pour 467231 ∈ COMPOSITE. Vous pouvez facilement vérifier que sur une feuille de papier sans le témoin donné, prouver que 467231 n’est pas premier serait difficile sans utiliser un ordinateur.
Nous n’avons rien dit sur la façon dont un témoin approprié peut être trouvé. C’est la partie non déterministe.
La classe NP contient tous les langages L pour lesquels il existe une machine de Turing V qui vérifie L et une constante k ∈ N telle que pour chaque entrée (w, c), V s’arrête après au plus T(|w/) étapes pour une fonction T ∈ O (n ↦ nk).
Notez que la définition ci-dessus implique que pour chaque w ∈ L il existe un témoin c avec |c|≤ T(|w/). (La machine de Turing ne peut pas regarder plus de symboles du témoin.)
NP est un surensemble de P (pourquoi ?). On ne sait pas s’il existe des langages qui sont dans NP mais pas dans P.
La factorisation d’entiers n’est pas un langage en soi. Cependant, nous pouvons construire un langage qui représente le problème de décision qui lui est associé. C’est-à-dire un langage qui contient tous les tuples (n, m) tels que n a un facteur d avec d & leq; m. Appelons ce FACTEUR de langage. Si vous avez un algorithme pour décider du FACTEUR, il peut être utilisé pour calculer une factorisation complète avec uniquement une surcharge polynomiale en effectuant une recherche binaire récursive pour chaque facteur premier.
Il est facile de montrer que le FACTEUR est en NP. Un témoin approprié serait simplement le facteur d lui-même et tout ce que le vérificateur aurait à faire est de vérifier que d & leq; m et n mod d = 0. Tout cela peut être fait en temps polynomial. (Rappelez-vous, encore une fois, que c’est la longueur de l’encodage qui compte et qui est logarithmique en n.)
Si vous pouvez montrer que ce FACTEUR est également en P, vous pouvez être sûr d’obtenir de nombreuses récompenses intéressantes. (Et vous avez brisé une partie importante de la cryptographie d’aujourd’hui.)
Pour chaque langage de NP, il existe un algorithme de force brute qui le décide de manière déterministe. Il effectue simplement une recherche exhaustive sur tous les témoins. (Notez que la longueur maximale d’un témoin est délimitée par un polynôme.) Donc, votre algorithme pour décider des NOMBRES PREMIERS était en fait un algorithme de force brute pour décider des COMPOSITES.
Pour répondre à votre dernière question, nous devons introduire une réduction. Les réductions sont un concept très puissant de l’informatique théorique. Réduire un problème à un autre signifie essentiellement résoudre un problème en résolvant un autre problème.
Soit Σ un alphabet et A et B des langues sur Σ. A est en temps polynomial plusieurs-un réductible à B s’il existe une fonction f : Σ＊ → Σ＊ avec les propriétés suivantes.
- w ∈ A ⇔ f(w)∈ B pour tout w ∈ Σ＊.
- La fonction f peut être calculée par une machine de Turing pour chaque entrée w en un certain nombre d’étapes délimitées par un polynôme dans |w|.
Dans ce cas, nous écrivons A ≤p B.
Par exemple, soit A le langage qui contient tous les graphiques (codés en matrice d’adjacence) qui contiennent un triangle. (Un triangle est un cycle de longueur 3.) Soit plus loin B le langage qui contient toutes les matrices avec une trace non nulle. (La trace d’une matrice est la somme de ses principaux éléments diagonaux.) Alors A est plusieurs fois polynomial réductible à B. Pour le prouver, nous devons trouver une fonction de transformation appropriée f. Dans ce cas, nous pouvons définir f pour calculer la 3ème puissance de la matrice d’adjacence. Cela nécessite deux produits matrice-matrice, chacun ayant une complexité polynomiale.
Il est trivialement vrai que L ≤p L. (Pouvez-vous le prouver formellement?)
Nous allons l’appliquer à NP maintenant.
Une langue L est NP-dure si et seulement si L ‘ ≤p L pour chaque langue L’∈ NP.
Un langage NP-hard peut être ou non en NP lui-même.
Un langage L est NP-complet si et seulement si
- L ∈ NP et
- L est NP-dur.
Le langage NP-complet le plus célèbre est SAT. Il contient toutes les formules booléennes qui peuvent être satisfaites. Par exemple, (a ∨ b) ∈ (a b b) ∈ SAT. Un témoin valide est {a= 1, b= 0}. La formule (a ∨ b) ( (a b b) b b SAT SAT. (Comment le prouveriez-vous ?)
Il n’est pas difficile de montrer que SAT ∈ NP. Montrer la dureté NP de la SAT est un travail, mais cela a été fait en 1971 par Stephen Cook.
Une fois qu’un langage NP-complet était connu, il était relativement simple de montrer la NP-complétude d’autres langages par réduction. Si le langage A est connu pour être NP-dur, alors montrer que A ≤p B montre que B est NP-dur aussi (via la transitivité de « ≤p »). En 1972, Richard Karp a publié une liste de 21 langues qu’il a pu montrer être NP-complètes via la réduction (transitive) de SAT. (C’est le seul article de cette réponse que je vous recommande réellement de lire. Contrairement aux autres, il n’est pas difficile à comprendre et donne une très bonne idée du fonctionnement de la preuve de NP-complétude via la réduction.)
Enfin, un bref résumé. Nous utiliserons les symboles NPH et NPC pour désigner les classes de langages NP-hard et NP-complete respectivement.
- P⊆ NP
- PNJ &sous-ensemble; NP et PNJ &sous-ensemble; NPH, en fait NPC = NP ∩ NPH par définition
- (A ∈ NP) ⇒(B ∈ NPH) ⇒ A ≤p B
Notez que l’inclusion NPC &sous-ensemble; NP est appropriée même dans le cas où P = NP. Pour voir cela, précisez qu’aucun langage non trivial ne peut être réduit à un langage trivial et qu’il existe des langages triviaux dans P ainsi que des langages non triviaux dans NP. C’est un cas de coin (pas très intéressant), cependant.
Votre principale source de confusion semble être que vous pensiez que le « n” dans « O(n ↦ f(n))” est l’interprétation de l’entrée d’un algorithme lorsqu’il fait référence à la longueur de l’entrée. C’est une distinction importante car cela signifie que la complexité asymptotique d’un algorithme dépend du codage utilisé pour l’entrée.
Cette semaine, un nouveau record pour le plus grand Mersenne prime connu a été atteint. Le plus grand nombre premier actuellement connu est 274 207 281 − 1 . Ce nombre est si énorme qu’il me donne mal à la tête, alors j’en utiliserai un plus petit dans l’exemple suivant: 231 – 1 = 2 147 483 647. Il peut être codé de différentes manières.
- par son exposant de Mersenne en tant que nombre décimal:
31(2 octets) - en tant que nombre décimal:
2147483647(10 octets) - en tant que nombre unaire:
11111…11où le…doit être remplacé par 2 147 483 640 autres1s (presque 2 GiO)
Toutes ces chaînes codent le même nombre et étant donné l’une d’elles, nous pouvons facilement construire n’importe quel autre codage du même nombre. (Vous pouvez remplacer l’encodage décimal par binaire, octal ou hexadécimal si vous le souhaitez. Il ne change la longueur que d’un facteur constant.)
L’algorithme naïf pour tester la primalité n’est polynomial que pour les codages unaires. Le test de primalité AKS est polynomial pour décimal (ou toute autre base b ≥ 2). Le test de primalité de Lucas-Lehmer est l’algorithme le plus connu pour les nombres premiers de Mersenne Mp avec p un nombre premier impair mais il est toujours exponentiel dans la longueur du codage binaire de l’exposant de Mersenne p (polynôme dans p).
Si nous voulons parler de la complexité d’un algorithme, il est très important que nous soyons très clairs sur la représentation que nous utilisons. En général, on peut supposer que l’encodage le plus efficace est utilisé. C’est-à-dire binaire pour les entiers. (Notez que tous les nombres premiers ne sont pas des nombres premiers de Mersenne, donc l’utilisation de l’exposant de Mersenne n’est pas un schéma de codage général.)
En cryptographie théorique, de nombreux algorithmes reçoivent formellement une chaîne complètement inutile de k 1s comme premier paramètre. L’algorithme ne regarde jamais ce paramètre mais il lui permet d’être formellement polynomial en k, qui est le paramètre de sécurité utilisé pour régler la sécurité de la procédure.
Pour certains problèmes pour lesquels le langage de décision en codage binaire est NP-complet, le langage de décision n’est plus NP-complet si le codage des nombres incorporés est commuté sur unaire. Les langages de décision pour d’autres problèmes restent NP-complets même alors. Ces derniers sont appelés fortement NP-complets. L’exemple le plus connu est l’emballage de poubelle.
Il est également (et peut-être plus) intéressant de voir comment la complexité d’un algorithme change si l’entrée est compressée. Pour l’exemple des nombres premiers de Mersenne, nous avons vu trois codages, chacun étant logarithmiquement plus compressé que son prédécesseur.
En 1983, Hana Galperin et Avi Wigderson ont écrit un article intéressant sur la complexité des algorithmes de graphe courants lorsque le codage d’entrée du graphe est compressé logarithmiquement. Pour ces entrées, le langage des graphes contenant un triangle d’en haut (où il était clairement en P) devient soudainement NP-complet.
Et c’est parce que les classes de langues comme P et NP sont définies pour les langues, pas pour les problèmes.