Vous avez fondamentalement raison sur P et NP, mais pas sur NP-hard et NP-complete.

Pour commencer, voici les définitions ultra-concises des quatre classes de complexité en question:

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

• NP est la classe des problèmes de décision qui peuvent être résolus en temps polynomial par une machine de Turing non déterministe. De manière équivalente, cest la classe des problèmes qui peuvent être vérifiés en temps polynomial par une machine de Turing déterministe.

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

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

Et ici « Diagramme sa Euler de Wikipedia montrant les relations entre ces quatre classes (en supposant que P nest pas égal à NP):

La partie que je suppose que vous « êtes la plus inconnue ou confuse par est la notion de « réduction polynomiale du temps » du problème X au problème Y. Une réduction de X à Y est simplement un algorithme A qui résout X en utilisant un autre algorithme B qui résout le problème Y. Cette réduction est appelée a  » réduction polynomiale du temps « si toutes les parties de A autres que B ont une complexité temporelle polynomiale. À titre dexemple trivial, le problème de la recherche du plus petit élément dun tableau est réductible en temps constant au problème de tri, puisque vous pouvez trier le tableau puis renvoyer le premier élément du tableau trié.

Un ce qui est facile à manquer à propos de la définition NP-hard, cest que la réduction passe des problèmes NP au problème NP-hard, mais pas nécessairement linverse . Cela signifie que les problèmes NP-hard peuvent être dans NP, ou dans une classe de complexité beaucoup plus élevée (comme vous pouvez le voir sur le diagramme dEuler), ou ils pourraient même ne pas être des problèmes décidables.Cest pourquoi les gens disent souvent quelque chose comme « NP-difficile signifie au moins aussi dur que NP » lorsquils essaient dexpliquer ce truc de manière informelle.

Le problème de larrêt est un bon exemple dun problème NP-difficile qui « nest clairement pas dans NP, comme Wikipédia lexplique :

Il est facile de prouver que le problème darrêt est NP-difficile mais pas NP-complet. Par exemple, le problème de satisfiabilité booléenne peut être réduit au problème darrêt en le transformant en la description dune machine de Turing qui essaie toutes les attributions de valeurs de vérité et quand elle en trouve une qui satisfait la formule, elle sarrête et sinon elle entre dans une boucle infinie. Il est également facile de voir que le problème darrêt nest pas dans NP puisque tous les problèmes dans NP sont décidables en un nombre fini dopérations, tandis que le problème darrêt, en général, est indécidable.

Commentaires

• @Nakano Intuitivement, il ‘ sa  » réduction  » dans le sens où un problème est en train de devenir un sous-problème dun autre problème. Le fait que certaines de ces réductions augmentent la complexité au lieu de la diminuer par un mauvais choix de  » subproblem  » signifie simplement que vous nutiliserez jamais ces réductions dans nimporte quel code du monde réel. Bien que pour être honnête, NP-hard me semble être une classe étrange et pas terriblement intéressante; il peut être plus utile de lignorer et de penser simplement à NP-complete comme lensemble des problèmes NP auxquels tous les autres problèmes NP se réduisent.
• @Nakano stackoverflow.com/questions/12637582/… Je pense que la réponse courte est que lorsque les gens disent que la factorisation entière est NP, ils ‘ parle normalement dentiers vraiment énormes, pour lesquels vous commencez généralement à faire vos preuves big-O avec n comme  » le nombre de bits que lentier prend en mémoire  » au lieu de  » le nombre dentiers que vous avez transmis à la fonction « .
• @Nakano: en notation big-O, le n est une mesure de la taille de lentrée (nombre déléments, doctets, de chiffres, etc.), et non de la valeur du
• @Nakano La réponse courte est que vous ‘ tout va bien, et cest pourquoi lorsque vous faites du temps co Lanalyse de la mplexité vous devez toujours spécifier ce que signifie n . Laffirmation selon laquelle n est  » la taille de lentrée  » est simplement un résumé concis de la façon dont nous choisissons normalement de définir n. Cela ‘ ne fait pas partie des définitions rigoureuses de la notation big-O ou de la complexité temporelle. Je crois que vous avez raison de dire que la factorisation entière est O (sqrt (n)) lorsque n est la valeur de lentrée. Il se trouve que les résultats de complexité où n signifie taille sont généralement beaucoup plus utiles en pratique que ceux où n signifie valeur.
• @Nakano It ‘ Il convient également de garder à lesprit que techniquement vous devez également définir la complexité temporelle de vos opérations primitives (addition, multitplication, lecture en mémoire, écriture en mémoire, comparaison de deux nombres). La plupart du temps, nous supposons que toutes ces primitives sont constantes ou nous ne comptons quun seul type dopération (par exemple, pour les algorithmes de tri, nous comptons traditionnellement les comparaisons). Je soupçonne que les résultats pour la factorisation entière don ‘ t supposent que toutes ces opérations sont en temps constant comme nous le faisons habituellement, sinon la taille du nombre ne ‘ t importe beaucoup.

La factorisation entière est citée comme exemple de NP, mais je ne comprends pas pourquoi ce nest pas P, personnellement, puisque la factorisation dessai prend du temps O (sqrt (n)).

Pour les besoins des classes de complexité, n est la longueur de lentrée. Donc, si vous voulez factoriser lentier k, n nest pas k mais log k, le nombre de bits (ou autre) quil faut pour écrire le nombre. La factorisation dentiers est donc O(sqrt(k)) comme vous le dites, mais cest O(sqrt(2n)) qui est O(2(n/2)).

NP-Hard Je suppose quil est juste plein dinconnues. Difficile à vérifier, difficile à résoudre.

Non. NP-Hard concerne simplement la difficulté à résoudre un problème.

Les problèmes NP-Hard sont au moins aussi difficiles que le problème le plus difficile de NP. Nous savons quils sont au moins aussi difficiles, car si nous avions un algorithme en temps polynomial pour un problème NP-Hard, nous pourrions adapter cet algorithme à nimporte quel problème de NP.

NP-Complet Je ne comprends pas du tout

NP- Complet signifie quun problème est à la fois NP et NP-Hard. Cela signifie que nous pouvons vérifier une solution rapidement (NP), mais cest au moins aussi difficile que le problème le plus difficile de NP (NP-Hard).

Je ne sais pas vraiment ce que signifie être non déterministe.

Non -déterminisme est une définition alternative de NP. Une machine de turing non déterministe est effectivement capable de se dupliquer à tout moment et de faire en sorte que chaque doublon emprunte un chemin dexécution différent. Selon cette définition, NP est lensemble des problèmes qui peuvent être résolus en temps polynomial par un ordinateur qui peut se dupliquer librement. Il savère que cest exactement le même ensemble de problèmes qui peuvent être vérifiés en temps polynomial.

Commentaires

• Il est donc possible pour $ O ( n ^ k) $ time algorithms to be NP problem?
• k est un nombre réel constant? Oui. Tous les problèmes P sont également des problèmes NP. Évidemment, tout ce que vous pouvez résoudre en temps polynomial peut également être vérifié en temps polynomial.
• Comment la longueur / taille est-elle réellement définie ici? Par exemple, je pourrais simplement écrire $ n $ dans une grande base et diminuer sa longueur lors de lécriture. Quen est-il des problèmes qui ne ‘ t traitent explicitement des entiers, mais disons des graphes avec des sommets $ V $ et des arêtes $ E $, etc.
• @Nakano, en fait une grande base ne la changerait pas ‘, car ce ne serait quune différence de facteur constante. Ainsi, cela neffectuerait pas ‘ t polynôme vs non polynomial. Cependant, si vous écriviez le nombre en unaire, cela le changerait.
• @Nakano, hmm … Je noserais ‘ essayer dexpliquer la complexité cours à un enfant de cinq ans. : P

La première chose à comprendre est que P et NP classe les langues , pas les problèmes . Pour comprendre ce que cela signifie, nous avons dabord besoin dautres définitions.

Un alphabet est un ensemble fini non vide de symboles.

{0 , 1} est un alphabet, tout comme le jeu de caractères ASCII. {} nest pas un alphabet car il est vide. N (les entiers) nest pas un alphabet car il nest pas fini.

Soit Σ être un alphabet. Une concaténation ordonnée dun nombre fini de symboles de Σ est appelée un mot over Σ .

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

Le longueur dun mot w , écrit comme | w |, est le nombre de symboles dedans.

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

Soit Σ être un alphabet. Lensemble Σ ^＊ contient tous les mots sur Σ , y compris ε . Lensemble Σ ⁺ contient tous les mots sur Σ , à lexclusion de ε . Pour n ∈ N , Σ ⁿ est lensemble des mots de longueur n .

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

{0, 1} ⁷ est lensemble des codes ASCII 7 bits {0000000, 0000001,…, 1111111}. {0, 1} ³² est lensemble des valeurs entières 32 bits.

Soit Σ un alphabet et L ⊆ Σ ^＊ . L est appelé une language over Σ .

Pour un alphabet Σ , le ensemble vide et Σ ^＊ sont des langues triviales sur Σ . La première est souvent appelée langue vide . La langue vide {} et la langue contenant uniquement le mot vide { ε } sont différentes.

Le sous-ensemble de {0, 1} ³² qui correspond aux 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. Lensemble des chaînes {1, 2,…} désignant les nombres entiers en notation décimale est une langue infinie sur lalphabet {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. Lensemble infini de chaînes {2, 3, 5, 7, 11, 13,…} désignant les nombres premiers en notation décimale en est un sous-ensemble propre. Le langage contenant tous les mots correspondant à lexpression régulière [+-]?\d+\.\d*([eE][+-]?\d+)? est un langage sur le jeu de caractères ASCII (indiquant un sous-ensemble des expressions à virgule flottante valides telles que définies par le langage de programmation C).

Il ny a pas de langage contenant tous les nombres réels (dans nimporte quelle notation) car lensemble des nombres réels nest pas dénombrable.

Soit Σ être un alphabet et L ⊆ Σ ^＊ . Une machine D décide L si pour chaque entrée w ∈ Σ ^＊ il calcule la fonction caractéristique χ _L ( 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 un décideur pour L . On écrit «  D ( w ) = x  » pour « donné w , D renvoie x ”.

Il existe de nombreux modèles de machines. Le modèle le plus général actuellement utilisé dans la pratique est le modèle dune machine de Turing . Une machine de Turing dispose dun stockage linéaire illimité regroupé en cellules. Chaque cellule peut contenir exactement un symbole dalphabet à tout moment. La machine de Turing effectue son calcul comme 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 dune position vers la cellule gauche ou droite. Laction que la machine va effectuer est contrôlée par un automate à états finis.

Une machine à accès aléatoire avec un ensemble fini dinstructions 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 suffirons plutôt à dire que la machine a une unité de contrôle déterministe finie, un stockage illimité et effectue un calcul comme une séquence détapes qui peut être compté.

Puisque vous « lavez utilisé dans votre question, je suppose que vous » êtes déjà familier avec la notation « big-O » donc voici seulement un rappel rapide.

Soit f : N → être une fonction.Lensemble O ( f ) contient toutes les fonctions g : N → N pour lesquels il existe des constantes n ₀ ∈ N et c ∈ N tels que pour chaque 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 sarrête après au plus T (| w |) pas pour une fonction T ∈ O ( n ↦ n ^k ).

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

Notez que la borne dépend de la longueur de w . Par conséquent, largument que vous faites pour la langue des nombres premiers nest correct que pour les nombres dans codages unaray , où pour le codage w de un nombre n , la longueur de lencodage | w | est proportionnel à n . Personne nutiliserait jamais un tel encodage dans la pratique. En utilisant un algorithme plus avancé que de simplement essayer tous les facteurs possibles, on peut montrer, cependant, que le langage des nombres premiers reste en P si les entrées sont codées en binaire (ou dans toute autre base). (Malgré un intérêt massif, cela na pu être prouvé que par Manindra Agrawal, Neeraj Kayal et Nitin Saxena dans un article primé en 2004, vous pouvez donc deviner que le algorithme nest pas très simple.)

Les langages triviaux {} et Σ ^＊ et la langue non triviale { ε } 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 chacun dentre eux et prouver que votre fonction a une complexité dexécution polynomiale?

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

Soit Σ un alphabet et L ⊆ Σ ^＊ . Une machine V qui prend un tuple encodé de deux mots w , c ∈ Σ ^＊ et renvoie 0 ou 1 après un nombre fini détapes est un verifier pour L sil a les propriétés suivantes.

• Donné ( w , c ), V renvoie 1 uniquement 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é un 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 nest cependant 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 la langue COMPOSITE, qui contient les encodages 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 que le témoin ne soit donné, il serait difficile de prouver que 467231 nest pas le premier sans utiliser un ordinateur.

Nous navons rien dit sur la façon dont un témoin approprié peut être Cest 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 input ( w , c ), V sarrête après au plus T (| w |) étapes pour une fonction T ∈ O ( n ↦ n^k ).

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 sur-ensemble de P (pourquoi?). On ne sait pas sil existe des langages qui sont en NP mais pas en P .

La factorisation dentiers nest pas un langage en soi. Cependant, nous pouvons construire un langage qui représente le problème de décision qui lui est associé. Cest-à-dire un langage 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 décider FACTOR, il peut être utilisé pour calculer une factorisation complète avec seulement un surcoût polynomial en effectuant une recherche binaire récursive pour chaque facteur premier.

Il est facile de montrer que FACTOR est dans NP . Un témoin approprié serait simplement le facteur d lui-même et tout ce que le vérificateur aurait à faire serait 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 cest la longueur de lencodage qui compte et que cest logarithmique en n .)

Si vous pouvez montrer que FACTOR est également dans P , vous pouvez être sûr de recevoir de nombreuses récompenses intéressantes. (Et vous avez brisé une partie importante de la cryptographie daujourdhui.)

Pour chaque langue de NP , il existe un algorithme de force brute qui décide il effectue une recherche déterministe. Il effectue simplement une recherche exhaustive sur tous les témoins. (Notez que la longueur maximale dun témoin est limitée par un polynôme.) Ainsi, votre algorithme pour décider PRIMES était en fait un algorithme de force brute pour décider COMPOSITE.

Pour répondre à votre dernière question, nous devons introduire la réduction . Les réductions sont un concept très puissant de linformatique 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 être des langues sur Σ . A est polynomial-time plusieurs-un réductible à B sil 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, on écrit A ≤ _p B .

Pour exemple, soit A le langage qui contient tous les graphiques (encodés comme matrice de contiguïté) qui contiennent un triangle. (Un triangle est un cycle de longueur 3.) Soit B plus le langage qui contient toutes les matrices avec trace non nulle. (La trace dune matrice est la somme de ses principaux éléments diagonaux.) Alors A est plusieurs-un en temps 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 puissance 3 ^rd de la matrice de contiguïté. 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 lappliquer maintenant à NP .

Une langue L est NP -hard si et seulement si L « ≤ _p L pour chaque langue L  » ∈ NP .

Un langage NP -hard peut ou non être dans NP lui-même.

Une langue L est NP -complete si et seulement si

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

Le langage NP complet le plus connu est SAT. Il contient toutes les formules booléennes qui peuvent ê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 prouveriez-vous cela?)

Il nest pas difficile de montrer que SAT ∈ NP . Montrer la NP dureté de SAT est un travail mais cela a été fait en 1971 par Stephen Cook .

Une fois quun langage NP complet était connu, il était relativement simple de montrer lexhaustivité NP dautres langages par réduction. Si la langue A est connue pour être NP -hard, alors montrer que A ≤ _p B montre que B est également NP -hard (via la transitivité de « ≤ _p ”). En 1972, Richard Karp a publié une liste de 21 langues quil pouvait montrer comme étant NP -complètes via la réduction (transitive) de SAT. (Cest le seul article de cette réponse que je vous recommande réellement de lire. Contrairement aux autres, il nest pas difficile à comprendre et donne une très bonne idée de la façon dont la preuve de lexhaustivité de NP par réduction fonctionne. )

Enfin, un petit résumé. Nous utiliserons les symboles NPH et NPC pour désigner les classes de langages NP -dur et NP -complets respectivement.

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

Notez que linclusion NPC ⊂ NP est correcte même dans le cas où P = NP . Pour voir cela, indiquez clairement quaucune langue non triviale ne peut être réduite à une langue triviale et quil existe également des langues triviales dans P comme langues non triviales dans NP . Thi s est un cas dangle (pas très intéressant), cependant.

Addendum

Votre principale source de confusion semble être que vous pensiez au « n »dans« O ( n ↦ f ( n )) ”Comme l interprétation de lentrée dun algorithme quand il se réfère en fait à la longueur de lentrée. Cest une distinction importante car cela signifie que la complexité asymptotique dun algorithme dépend du encodage utilisé pour lentrée.

Cette semaine, un nouvel enregistrement pour le plus grand Mersenne prime a été atteint. Le plus grand nombre premier actuellement connu est 2 ^{74   207   281} – 1. Ce nombre est tellement énorme que cela me donne mal à la tête, alors jen utiliserai un plus petit dans lexemple suivant: 2 ³¹ – 1 = 2   147   483   647. Il peut être encodé de différentes manières.

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

Toutes ces chaînes encodent le même nombre et étant donné lune dentre elles, nous pouvons facilement construire nimporte quel autre encodage du même nombre. (Vous pouvez remplacer lencodage décimal par binaire, octal ou hexadéci mal si vous le souhaitez. Il ne modifie la longueur que par un facteur constant.)

Lalgorithme naïf pour tester la primalité nest polynomial que pour les encodages 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 lalgorithme le plus connu pour les nombres premiers de Mersenne M _p avec p un premier impair mais il est toujours exponentiel dans la longueur du codage binaire de lexposant de Mersenne p (polynôme en p ).

Si nous voulons parler de la complexité dun 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 le codage le plus efficace est utilisé. Autrement dit, binaire pour les entiers. (Notez que tous les nombres premiers ne sont pas des nombres premiers de Mersenne, donc lutilisation de lexposant de Mersenne nest pas un schéma dencodage général.)

En cryptographie théorique, de nombreux algorithmes reçoivent formellement une chaîne complètement inutile de k 1 s comme premier paramètre. Lalgorithme 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 dans lencodage binaire est NP -complet, le langage de décision nest plus NP -complète si le codage des nombres incorporés est commuté sur unaire. Les langages de décision pour les autres problèmes restent NP -complets même alors. Ces derniers sont appelés fortement NP -complets . Lexemple le plus connu est bin packing .

Il est également (et peut-être plus) intéressant de voir comment la complexité dun algorithme change si lentrée est compressée . Pour lexemple des nombres premiers de Mersenne, nous avons vu trois encodages, chacun étant logarithmiquement plus compressé que son prédécesseur.

En 1983, Hana Galperin et Avi Wigderson a écrit un article intéressant sur la complexité des algorithmes de graphe courants lorsque le codage dentrée du graphe est compressé de manière logarithmique. Pour ces entrées, le langage des graphiques contenant un triangle den haut (où il était clairement en P ) devient soudainement NP -complet.

Et cela « parce que les classes de langue comme P et NP sont définies pour les langues , pas pour les problèmes .

Commentaires

• Cette réponse nest probablement pas utile pour le niveau de compréhension du demandeur. Lisez les autres réponses et voyez ce avec quoi Nanako se débat. Pensez-vous que ceci réponse va laider?
• Cette réponse naidera peut-être pas OP, mais aidera certainement les autres lecteurs (moi y compris).
• réponse très utile! devrait envisager de corriger les symboles mathématiques de manière incorrecte affiché.

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

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

Problème NP: problèmes qui peuvent être vérifiés dans polyno temps mial. Par exemple: vendeur itinérant, conception de circuits. Les problèmes de NP sont un peu comme des énigmes (comme le sudoku). Étant donné une solution correcte pour le problème, nous pouvons vérifier notre solution très rapidement, mais si nous essayons réellement de la résoudre, cela pourrait prendre une éternité.

Maintenant, P vs NP demande en fait si un problème dont la solution peut être rapide vérifié pour être correct, alors existe-t-il toujours un moyen rapide de le résoudre. Donc écrire 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 NP. Par conséquent, sil existe un moyen plus rapide de résoudre NP complet, alors NP complet devient P et les problèmes NP se réduisent en P.

NP difficile: 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 aux échecs en fait partie.

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

Jespère que cela fournira un contour flou.