J'essaie de comprendre ces classifications et pourquoi elles existent. Ma compréhension est-elle correcte? Si non quoi?

1. P est la complexité polynomiale, ou pour un nombre réel non négatif , tel que , etc. Si un problème appartient à P, il existe au moins un algorithme capable de le résoudre à partir de zéro en temps polynomial. Par exemple, je peux toujours déterminer si un entier est premier en effectuant une boucle et en vérifiant à chaque étape si elle se divise .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP est une complexité polynomiale non déterministe. Je ne sais pas vraiment ce que cela signifie pour que ce soit non déterministe. Je pense que cela signifie qu'il est facile de vérifier en temps polynomial, mais que ce n'est peut-être pas toujours le temps polynomial à résoudre à partir de zéro si nous ne connaissions pas déjà la réponse. Comme il peut être résolu en temps polynomial, tous les problèmes de P sont également des problèmes de NP. La factorisation de nombre entier est citée comme exemple de NP, mais je ne comprends pas pourquoi ce n’est pas P, personnellement, car la factorisation d’essai prend du O(sqrt(n))temps.

3. NP-Complete Je ne comprends pas du tout, mais le problème du voyageur de commerce est cité en exemple. Mais à mon avis, le problème du TSP pourrait bien être un problème de NP, car il faut quelque chose comme pour vérifier si le chemin vous est donné au départ.O(2n n2) time to solve, but O(n)

4. NP-Hard Je suppose que c'est juste plein d'inconnues. Difficile à vérifier, difficile à résoudre.

Vous avez fondamentalement raison sur P et NP, mais pas sur NP-dur et NP-complet.

Pour commencer, voici les définitions très concises des quatre classes de complexité en question:

• P est la classe de problèmes de décision pouvant être résolus en temps polynomial par une machine de Turing déterministe.

• NP est la classe de problèmes de décision pouvant être résolus en temps polynomial par une machine de Turing non déterministe. De manière équivalente, c'est la classe de problèmes qui peut être vérifiée en temps polynomial par une machine de Turing déterministe.

• NP-hard est la classe de problèmes de décision auxquels tous les problèmes de NP peuvent être réduits en temps polynomial par une machine de Turing déterministe.

• NP-complet est l'intersection de NP-hard et NP. De manière équivalente, NP-complet est la classe de problèmes de décision dans NP à laquelle tous les problèmes de NP peuvent être réduits en temps polynomial par une machine de Turing déterministe.

Et voici un diagramme d'Euler de Wikipedia montrant les relations entre ces quatre classes (en supposant que P n'est pas égal à NP):

La partie qui, je suppose, vous est le moins familier ou qui vous déconcerte le plus est la notion de "réduction de temps polynomiale" d'un problème X à un problème Y. Une réduction de X à Y est simplement un algorithme A qui résout X en utilisant autre algorithme B qui résout le problème Y. Cette réduction est appelée "réduction du temps polynomial" si toutes les parties de A autres que B ont une complexité de temps polynomiale. Comme exemple trivial, le problème de la recherche du plus petit élément dans un tableau est réductible à temps constant au problème de tri, car vous pouvez trier le tableau puis renvoyer le premier élément du tableau trié.

Une chose qui manque facilement dans la définition de NP-hard est que la réduction va du problème de NP au problème de NP-difficile, mais pas nécessairement l'inverse . Cela signifie que les problèmes NP-durs peuvent appartenir à NP ou à une classe de complexité beaucoup plus élevée (comme le montre le diagramme d'Euler), ou encore ne pas être des problèmes résolus. C'est pourquoi les gens disent souvent quelque chose comme "NP-hard signifie au moins aussi dur que NP" lorsqu'ils essaient d'expliquer ces choses de manière informelle.

Le problème d’arrêt est un bon exemple de problème NP-difficile qui n’apparaît clairement pas dans NP, comme l'explique Wikipedia :

Il est facile de prouver que le problème d’arrêt est NP-difficile mais pas complet. Par exemple, le problème de satisfiabilité booléenne peut être réduit au problème bloquant en le transformant en description d'une machine de Turing qui tente toutes les attributions de valeurs de vérité et lorsqu'elle en trouve une qui satisfait à la formule, elle s'arrête et sinon elle passe dans une boucle infinie. Il est également facile de voir que le problème d’arrêt n’est pas dans NP car tous les problèmes dans NP sont décidables en un nombre fini d’opérations, tandis que le problème d’arrêt, en général, est indécidable.

La factorisation de nombre entier est citée comme exemple de NP, mais je ne comprends pas pourquoi ce n’est pas P, personnellement, car la factorisation d’essai prend du temps O (sqrt (n)).

Pour les besoins des classes de complexité, le nest la longueur de l'entrée. Donc, si vous voulez factoriser un entier k, nn’est pas, kmais log kle nombre de bits (ou peu importe) qu’il faut pour écrire le nombre. Donc, la factorisation entière est O(sqrt(k))comme vous le dites, mais c'est ce qui est .O(sqrt(2n))O(2(n/2))

NP-Hard Je suppose que c'est juste plein d'inconnues. Difficile à vérifier, difficile à résoudre.

NP-Hard ne concerne que la difficulté à résoudre un problème.

Les problèmes NP-Hard sont au moins difficiles à résoudre car ils constituent le problème le plus difficile en NP. Nous savons qu'ils sont au moins aussi difficiles, car si nous avions un algorithme polynomial pour un problème NP-Hard, nous pourrions l'adapter à n'importe quel problème de NP.

NP-Complete Je ne comprends pas du tout

NP-Complete signifie qu'un problème est à la fois NP et NP-Hard. Cela signifie que nous pouvons vérifier rapidement une solution (NP), mais au moins aussi difficile que le problème le plus difficile en NP (NP-Hard).

Je ne sais pas vraiment ce que cela signifie pour que ce soit non déterministe.

Le non-déterminisme est une définition alternative du NP. Une machine de turing non déterministe est capable de se dupliquer à tout moment, et chaque duplicata prend un chemin d'exécution différent. Selon cette définition, NP est l’ensemble des problèmes pouvant être résolus en temps polynomial par un ordinateur et pouvant se reproduire librement. Il s’avère que c’est exactement le même ensemble de problèmes que l’on peut vérifier en temps polynomial.

La première chose à comprendre est que P et NP classifient les langues , 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 de symboles non vides.

{ 0, 1} est un alphabet comme le jeu de caractères ASCII. {} n'est pas un alphabet parce qu'il est vide. N (les entiers) n'est pas un alphabet parce qu'il n'est pas fini.

Que Σ un alphabet. Une concaténation ordonnée d'un nombre fini de symboles de Σ est appelé un mot sur Σ .

La chaîne 101est un mot sur l'alphabet { 0, 1}. Le mot vide (souvent écrit comme ε ) est un mot sur n'importe quel alphabet. La chaîne penguinest un mot sur l'alphabet contenant les caractères ASCII. La notation décimale du nombre π est pas un mot sur l'alphabet { ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} parce que ce n'est pas fini.

La longueur d'un mot w , écrit comme | w |, est le nombre de symboles qu'il contient.

Par exemple | hello| = 5 et | ε | = 0. Pour tout mot w , | w | ∈ N et donc fini.

Que Σ un alphabet. L'ensemble Σ ^* contient tous les mots sur Σ , y compris ε . L'ensemble Σ ⁺ contient tous les mots sur Σ , à l' exclusion ε . Pour n ∈ N , Σ ⁿ est l'ensemble des mots de longueur n .

Pour chaque alphabet Σ , Σ ^* et Σ ⁺ sont infinies ensembles dénombrables . Pour le jeu de caractères ASCII Σ _ASCII , les expressions régulières .*et .+représentent Σ _ASCII ^* et Σ _ASCII ⁺ respectivement.

{ 0, 1} ⁷ est l'ensemble des codes ASCII 7 bits { 0000000, 0000001..., 1111111}. { 0, 1} ³² est l'ensemble des valeurs entières de 32 bits.

Que Σ un alphabet et L ⊆ Σ ^* . L est appelé un langage sur Σ .

Pour un alphabet Σ , l'ensemble vide et Σ ^* sont des langues triviales 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 { 0, 1} ³² qui correspond à des valeurs à virgule flottante IEEE 754 non-NaN est un langage fini.

Les langues peuvent avoir un nombre infini de mots mais chaque langue est dénombrable. L'ensemble des chaînes { 1, 2...} désignant les nombres entiers en notation décimale est un langage infini sur l'alphabet { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. L'ensemble infini de chaînes { 2, 3, 5, 7, 11, 13, ...} désignant les nombres premiers en notation décimale est un sous - ensemble de celui - ci approprié. Le langage contenant tous les mots correspondant à l'expression régulière [+-]?\d+\.\d*([eE][+-]?\d+)?est un langage recouvrant le jeu de caractères ASCII (désignant un sous-ensemble des expressions à virgule flottante valides définies par le langage de programmation C).

Il n'y a pas de langue contenant tous les nombres réels (quelle que soit la notation) car l'ensemble des nombres réels n'est pas dénombrable.

Que Σ un alphabet et L ⊆ Σ ^* . Machine D décide L si pour chaque entrée w ∈ Σ ^* il calcule la fonction caractéristique de _{la L} ( w ) en temps fini. La fonction caractéristique est définie comme

χ L : Σ * → {0, 1}
     w   ↦ 1,   w ∈ L 
         0, sinon.

Une telle machine est appelée decider pour L . On écrit “ D ( w ) = x ” pour “étant donné w , D sorties x ”.

Il existe de nombreux modèles de machines. Le modèle le plus courant et le plus couramment utilisé aujourd'hui est le modèle d'une machine de Turing . Une machine de Turing possède 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 de gauche ou de 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 d'instructions finies 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 embêterons pas avec le modèle de machine précis que nous utilisons, mais nous dirons simplement que la machine possède une unité de contrôle déterministe finie, une mémoire illimitée et effectue un calcul sous forme d'une séquence d'étapes pouvant être comptées.

Comme vous l'avez utilisé dans votre question, je suppose que vous connaissez déjà la notation «big-O» . Voici donc un rapide rappel.

Soit f : N → une fonction. L'ensemble O ( f ) contient toutes les fonctions g : N → N pour lesquels il existe des constantes n ₀ ∈ N et c ∈ N tel que pour tout n ∈ N avec n > n ₀ il est vrai que g ( n ) ≤ c f ( n ).

Nous sommes maintenant prêts à aborder la vraie question.

La classe P contient toutes les langues L pour lesquelles 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 |) pas pour une fonction T ∈ O ( n ↦ n ^k ).

Puisque O ( n ↦ n ^k ), bien que mathématiquement correct, ne soit pas pratique pour écrire et lire, la plupart des gens - pour être honnête, tout le monde sauf moi - écrit habituellement simplement O ( n ^k ).

Notez que la limite dépend de la longueur de w . Par conséquent, l'argument que vous développez pour la langue des nombres premiers n'est correct que pour les nombres en codages superflus , où pour le codage w d'un nombre n , la longueur du codage | w | est proportionnelle à n . Personne n’utiliserait un tel encodage en pratique. En utilisant un algorithme plus avancé que simplement essayer tous les facteurs possibles, on peut montrer que le langage des nombres premiers reste en P si les entrées sont codées en binaire (ou à toute autre base). (En dépit d’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 langues triviales {} et Σ ^* et le langage non trivial { ε } sont évidemment 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’elles et prouvent que votre fonction a une complexité d’exécution polynomiale?

Chaque régulière langue (une langue décrite par une expression régulière) est en P .

Que Σ un alphabet et L ⊆ Σ ^* . Machine V qui prend un tuple de deux mots codés w , c ∈ Σ ^* et sorties 0 ou 1 après un nombre fini d'étapes est un vérificateur de L si elle a les propriétés suivantes.

• Étant donné ( p , c ), V sorties 1 seulement si w ∈ L .
• Pour tout w ∈ L , il existe un c ∈ Σ ^* tel que V ( w , c ) = 1.

Le c dans la définition ci-dessus s'appelle un témoin (ou un certificat ).

Un vérificateur est autorisé à donner des faux négatifs pour le mauvais témoin , même si w est en fait en L . Il n'est toutefois pas permis de 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 non premiers, un témoin peut être une factorisation. Par exemple, (659, 709)est témoin de 467231∈ COMPOSITE. Vous pouvez facilement vérifier cela sur une feuille de papier alors que le témoin n’est pas indiqué, prouver que 467231 n’est pas primordial serait difficile sans l’utilisation d’un ordinateur.

Nous n'avons rien dit sur la façon de trouver un témoin approprié. C'est la partie non déterministe.

La classe NP contient toutes les langues L pour lesquelles 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 ↦ n ^k ).

Notez que la définition ci-dessus implique qu'il existe pour chaque w ∈ L un témoin c avec | c | ≤ T (| w |). (La machine de Turing ne peut éventuellement pas regarder plus de symboles du témoin.)

NP est un sur-ensemble de P (pourquoi?). On ne sait pas s'il existe des langages qui sont NP , mais pas dans P .

La factorisation d'entiers n'est pas une langue en soi. Cependant, nous pouvons construire un langage qui représente le problème de décision qui lui est associé. Autrement dit, une langue qui contient tous les tuples ( n , m ) tels que n a un facteur d avec d ≤ m . Appelons ce langage FACTOR. Si vous avez un algorithme pour choisir FACTOR, 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 FACTOR 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 ≤ 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 que c'est logarithmique dans n .)

Si vous pouvez montrer que FACTOR est également en P , vous pouvez être sûr d'obtenir de nombreuses récompenses intéressantes. (Et vous avez cassé une partie importante de la cryptographie d'aujourd'hui.)

Pour chaque langue 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.) Ainsi, votre algorithme pour décider de PRIMES était en réalité un algorithme de force brute pour décider de COMPOSITE.

Pour répondre à votre dernière question, nous devons introduire la réduction . Les réductions sont un concept très puissant de l'informatique théorique. Réduire un problème en un autre signifie fondamentalement résoudre un problème en résolvant un autre.

Que Σ un alphabet et A et B sont des langues sur Σ . A est polynomial beaucoup-un réductibles à B s'il existe une fonction f : Σ ^* → Σ ^* avec les propriétés suivantes.

• w ∈ A   ⇔   f ( w ) ∈ B   pour tous w ∈ Σ ^* .
• La fonction f peut être calculée par une machine de Turing pour chaque entrée w dans un nombre d'étapes limité par un polynôme dans | w |.

Dans ce cas, nous écrivons A de _p B .

Par exemple, prenons A comme langage qui contient tous les graphes (codés sous forme de matrice de contiguïté) contenant un triangle. (Un triangle est un cycle de longueur 3.) Soit B le langage qui contient toutes les matrices dont le tracé est non nul. (La trace d'une matrice est la somme de ses principaux éléments diagonaux). Puis A est polynomial nombre-one réductibles à B . Pour le prouver, nous devons trouver une fonction de transformation appropriée f . Dans ce cas, nous pouvons configurer 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 vrai que trivialement 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 .

Une langue dure- NP peut être ou ne pas être en NP même.

Une langue L est NP -complete si et seulement si

• L ∈ NP et
• L est NP -hard.

Le langage le plus connu du NP- complet est le SAT. Il contient toutes les formules booléennes pouvant être satisfaites. Par exemple, ( a ∨ b ) (¬ a ∨ ¬ b ) SAT. Un témoin valide est { a = 1, b = 0}. La formule ( a ∨ b ) (¬ a ∨ b ) ¬ b ∉ SAT. (Comment le prouverais-tu?)

Il n'est pas difficile de montrer que SAT NP . Montrer la dureté NP de la SAT est un travail qui a été réalisé en 1971 par Stephen Cook .

Une fois que cette langue complète - NP était connue, il était relativement simple de montrer la complétude NP des autres langues par réduction. Si le langage A est connu pour être NP -Hard, puis montrer que A de _p B de montre que B est NP -Hard aussi (via la transitivité de « ≤ _p »). En 1972, Richard Karp publia une liste de 21 langues qu’il pouvait montrer: NP- complète par réduction (transitive) de la SAT. (C’est le seul document de cette réponse que je vous recommande en réalité de lire. Contrairement aux autres, il n’est pas difficile à comprendre et donne une très bonne idée de la façon dont prouver le caractère complet de NP via une réduction fonctionne.)

Enfin, un bref résumé. Nous utiliserons les symboles NPH et NPC pour désigner les classes des langages NP -hard et NP- complet .

• P ⊆ NP
• NPC ⊂ NP et NPC ⊂ NPH , en fait NPC = NP ∩ NPH par définition
• ( A ∈ NP ) ( B ∈ NPH ) ⇒   A ≤ _p B

Notez que l'inclusion NPC ⊂ NP est appropriée même dans le cas où P = NP . Pour voir cela, précisez clairement qu'aucun langage non trivial ne peut être réduit à un langage trivial et qu'il existe des langages triviaux en P ainsi que des langages non triviaux en NP . C'est un corner (pas très intéressant), cependant.

Addenda

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. Cette distinction est importante car elle 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 prime de Mersenne connue a été atteint. Le plus grand nombre premier connu à ce jour est 2 ^{74 207 281} - 1. Ce nombre est si énorme qu'il me donne mal à la tête, je vais donc en utiliser un plus petit dans l'exemple suivant: 2 ³¹ - 1 = 2 147 483 647. être codé de différentes manières.

• par son exposant de Mersenne sous forme décimale: 31(2 octets)
• sous forme décimale: 2147483647(10 octets)
• comme numéro unaire: 11111…11où le …doit être remplacé par 2 147 483 640 1s (presque 2 Gio)

Toutes ces chaînes encodent le même nombre et, étant donné l’une quelconque de celles-ci, nous pouvons facilement construire tout autre encodage du même nombre. (Vous pouvez remplacer l'encodage décimal par binaire, octal ou hexadécimal si vous le souhaitez. Cela ne change que la longueur par un facteur constant.)

L'algorithme naïf pour tester la primalité n'est qu'un polynôme pour les codages unaires. Le test de primalité AKS est polynomial pour décimal (ou toute autre base b ≥ 2). Le Lucas-Lehmer test de primalité est le meilleur algorithme connu pour les nombres premiers de Mersenne M _p avec p un nombre premier impair , mais il est encore exponentielle de la longueur du codage binaire de l'exposant Mersenne p (polynôme en p ).

Si nous voulons parler de la complexité d'un algorithme, il est très important que nous sachions très clairement quelle représentation nous utilisons. En général, on peut supposer que le codage le plus efficace est utilisé. C'est-à-dire, binaire pour les entiers. (Notez que chaque nombre premier n'est pas un nombre premier de Mersenne, utiliser l'exposant de Mersenne n'est donc 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 1 s en tant que premier paramètre. L'algorithme ne regarde jamais ce paramètre, mais il lui permet d'être formellement polynomial dans k , qui est le paramètre de sécurité utilisé pour optimiser la sécurité de la procédure.

Pour certains problèmes pour lesquels le langage de décision du codage binaire est NP- complet, le langage de décision n'est plus NP- complet si le codage des nombres incorporés est basculé sur unaire. Les langues de décision pour les autres problèmes restent NP- complètes même dans ce cas. Ces derniers sont appelés fortement NP- complets . L'exemple le plus connu est celui de la corbeille .

Il est également intéressant (et peut-être davantage) 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 rédigé un article intéressant sur la complexité des algorithmes de graphes communs lorsque le codage en entrée du graphe est compressé de manière logarithmique. 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 telles que P et NP sont définies pour des langues et non pour des problèmes .

Je vais essayer de vous donner une définition moins informelle pour la même chose.

P problèmes: problèmes qui peuvent être résolus en temps polynomial. Contient des problèmes pouvant être résolus efficacement.

Problème NP: problèmes qui peuvent être vérifiés en temps polynomial. Par exemple: voyageur de commerce, conception de circuit. Les problèmes de NP sont un peu comme des énigmes (comme le sudoku). Si la solution au problème est correcte, nous pouvons vérifier notre solution très rapidement, mais si nous essayons réellement de le résoudre, cela risque de prendre une éternité.

Maintenant, P vs NP demande en fait si un problème dont la solution peut être vérifiée rapidement est correct, alors existe-t-il toujours un moyen rapide de le résoudre. Ainsi, écrivant en termes mathématiques: NP est-il un sous-ensemble de P ou non?

Revenons maintenant à NP complet: ce sont les problèmes vraiment difficiles des problèmes de NP. Par conséquent, s'il existe un moyen plus rapide de résoudre le NP complet, alors le NP complet devient P et les problèmes NP disparaissent en P.

NP hard: les problèmes qui ne peuvent même pas être vérifiés dans le temps polynomial sont np difficiles. Par exemple, choisir le meilleur coup d'échecs est l'un d'entre eux.

Si quelque chose vous échappe, essayez de regarder cette vidéo: https://www.youtube.com/watch?v=YX40hbAHx3s

J'espère que cela fournira des contours flous.