Qu'est-ce que "P = NP?" Et pourquoi est-ce une question aussi célèbre? [fermé]

Question

La question de savoir si P = NP est peut-être le plus célèbre de toutes les sciences informatiques. Qu'est-ce que ça veut dire? Et pourquoi est-ce si intéressant?

Oh, et pour plus de crédit, postez une preuve de la vérité ou de la fausseté de votre déclaration. :)

Answer 1

P représente le temps polynomial. NP représente le temps polynomial non déterministe.

Définitions:

• Le temps polynomial signifie que la complexité de l'algorithme est de O (n ^ k), où n est la taille de vos données (par exemple, le nombre d'éléments d'une liste à trier). et k est une constante.

La

• complexité correspond au temps, exprimé en nombre d'opérations, en fonction du nombre d'éléments de données.

• L'opération est ce qui convient le mieux en tant qu'opération de base pour une tâche particulière. Pour trier l’opération de base est une comparaison. Pour la multiplication matricielle, l’opération de base est la multiplication de deux nombres.

Maintenant, la question est de savoir ce que signifie déterministe et non déterministe. Il existe un modèle de calcul abstrait, un ordinateur imaginaire appelé machine de Turing (TM). Cette machine a un nombre fini d'états et une bande infinie, qui comporte des cellules discrètes dans lesquelles un ensemble fini de symboles peut être écrit et lu. A tout moment, le TM se trouve dans l'un de ses états et examine une cellule particulière de la bande. Selon ce qu'il lit dans cette cellule, il peut écrire un nouveau symbole dans cette cellule, déplacer la bande d'une cellule vers l'avant ou vers l'arrière et passer à un état différent. Ceci s'appelle une transition d'état. Étonnamment, en construisant avec soin les états et les transitions, vous pouvez concevoir une MT, qui équivaut à tout programme informatique pouvant être écrit. C'est pourquoi il est utilisé comme modèle théorique pour prouver ce que les ordinateurs peuvent et ne peuvent pas faire.

Deux types de MT nous concernent ici: les déterministes et les non-déterministes. Un TM déterministe n'a qu'une transition de chaque état pour chaque symbole lu sur la bande. Une MT non déterministe peut avoir plusieurs transitions de ce type: i. e. il est capable de vérifier plusieurs possibilités simultanément. C'est un peu comme créer plusieurs threads. La différence est qu’une MT non déterministe peut engendrer autant de tels "threads". comme il le souhaite, alors que sur un ordinateur réel, seul un nombre spécifique de threads peut être exécuté à la fois (égal au nombre de processeurs). En réalité, les ordinateurs sont fondamentalement des MT déterministes avec des bandes finies. D'autre part, une MT non déterministe ne peut pas être réalisée physiquement, sauf peut-être avec un ordinateur quantique.

Il a été prouvé que tout problème pouvant être résolu par une MT non déterministe peut être résolu par une MT déterministe. Cependant, on ne sait pas combien de temps cela va prendre. La déclaration P = NP signifie que si un problème prend du temps polynomial sur une MT non déterministe, alors on peut construire une MT déterministe qui résoudrait le même problème également en temps polynomial. Jusqu'à présent, personne n'a été en mesure de démontrer que cela pouvait être fait, mais personne n'a été en mesure de prouver que cela ne pouvait pas être fait.

Problème NP-complet signifie un problème X de NP, de sorte que tout problème NP de Y peut être réduit à X par une réduction polynomiale. Cela implique que si jamais quelqu'un trouve une solution polynomiale à un problème NP-complet, cela donnera également une solution polynomiale à tout problème NP. Cela prouverait donc que P = NP. Inversement, si quelqu'un devait prouver que P! = NP, nous serions certains qu'il n'y a aucun moyen de résoudre un problème de NP en temps polynomial sur un ordinateur conventionnel.

Un exemple de problème NP-complet est le problème de la recherche d'une affectation de vérité permettant de rendre une expression booléenne contenant n variables vraie.
Pour le moment, dans la pratique, tout problème prenant du temps polynomial sur une MT non déterministe ne peut être résolu que de manière exponentielle sur un MT déterministe ou sur un ordinateur conventionnel.
Par exemple, le seul moyen de résoudre le problème de l’affectation de la vérité est d’essayer 2 possibilités sur ^ n.

Answer 2

1. Un problème de type oui ou non se trouve dans P ( P heure olynomiale) si la réponse peut être calculée en temps polynomial.
2. Un problème de type oui ou non se trouve dans NP ( N sur le temps déterministe P ) si une réponse positive peut être < em> vérifié en temps polynomial.

Intuitivement, nous pouvons voir que si un problème se trouve dans P , il se trouve dans NP . Étant donné la réponse potentielle à un problème dans P , nous pouvons vérifier la réponse en recalculant simplement la réponse.

Il est moins évident, et beaucoup plus difficile de répondre, de déterminer si tous les problèmes de NP se situent dans P . Le fait de pouvoir vérifier une réponse en temps polynomial signifie-t-il que nous pouvons calculer cette réponse en temps polynomial?

Il existe un grand nombre de problèmes importants connus pour être NP complets (en gros, s'il s'avère que ces problèmes se trouvent dans P , alors tous les NP se sont révélés être dans P ). Si P = NP , il sera prouvé que tous ces problèmes ont une solution efficace (à temps polynomial).

La plupart des scientifiques pensent que le P ! = NP . Toutefois, aucune preuve n'a encore été établie pour P = NP ou pour P ! = NP . s'il gagne une preuve de conjecture, il gagnera 1 million de dollars US .

Answer 3

Pour donner la réponse la plus simple à laquelle je puisse penser:

Supposons que nous ayons un problème prenant un certain nombre d’intrants et offrant diverses solutions potentielles, qui peuvent ou non résoudre le problème pour des intrants donnés. Un casse-tête logique dans un magazine de casse-tête serait un bon exemple: les entrées sont les conditions ("George ne vit pas dans la maison bleue ou verte"), et la solution potentielle est une liste d'énoncés ("George habite dans la maison jaune, cultive des pois et possède le chien "). Un exemple célèbre est le problème du vendeur itinérant: étant donné la liste des villes et les temps nécessaires pour se rendre d’une ville à l’autre, et une heure limite, une solution potentielle serait une liste des villes dans l’ordre dans lequel le vendeur les visite, et cela fonctionnerait si la somme des temps de trajet était inférieure à la limite de temps.

Un tel problème se pose chez NP si nous pouvons vérifier efficacement une solution potentielle pour voir si elle fonctionne. Par exemple, à partir d’une liste de villes que le vendeur doit visiter dans l’ordre, nous pouvons additionner les heures de chaque voyage entre les villes et voir facilement si le temps est écoulé. Un problème est dans P si nous pouvons efficacement trouver une solution s'il en existe une.

(Efficacement, ici, a une signification mathématique précise. Concrètement, cela signifie que les grands problèmes ne sont pas excessivement difficiles à résoudre. Lorsque vous recherchez une solution possible, il serait inefficace de répertorier toutes les solutions possibles, ou quelque chose de différent. proche de cela, alors qu’un moyen efficace nécessiterait de chercher un ensemble beaucoup plus limité.)

Par conséquent, le problème P = NP peut être exprimé de la manière suivante: Si vous pouvez vérifier efficacement une solution à un problème du type décrit ci-dessus, pouvez-vous trouver une solution (ou prouver qu’il n’en existe pas) de manière efficace? La réponse évidente est "Pourquoi devriez-vous pouvoir le faire?" Et c’est à peu près ce dont il s’agit aujourd’hui. Personne n'a été capable de le prouver d'une manière ou d'une autre et cela dérange beaucoup de mathématiciens et d'informaticiens. C’est pourquoi tous ceux qui peuvent prouver que la solution proposée par la Fondation Claypool coûtent un million de dollars.

Nous supposons généralement que P n’est pas égal à NP, qu’il n’existe aucun moyen général de trouver des solutions. S'il s'avérait que P = NP, beaucoup de choses changeraient. Par exemple, la cryptographie deviendrait impossible et entraînerait toute sorte de vie privée ou de vérifiabilité sur Internet. Après tout, nous pouvons efficacement prendre le texte crypté et la clé et produire le texte original. Ainsi, si P = NP, nous pourrions efficacement trouver la clé sans le savoir à l’avance. La fissuration du mot de passe deviendrait triviale. Par ailleurs, il existe des classes entières de problèmes de planification et d’affectation des ressources que nous pourrions résoudre efficacement.

Vous avez peut-être entendu la description NP-complete. Un problème NP-complet est un problème NP (bien sûr), et a cette propriété intéressante: s'il est dans P, chaque problème NP est, et donc P = NP. Si vous pouviez trouver un moyen de résoudre efficacement le problème Travelling Salesman, ou des énigmes logiques tirées de magazines de casse-tête, vous pourriez résoudre efficacement n'importe quoi en NP. Un problème NP-complet est, d’une certaine manière, le problème le plus difficile à résoudre.

Ainsi, si vous pouvez trouver une technique efficace de résolution générale de tout problème NP-complet ou prouver que vous n'en avez pas, la renommée et la fortune vous appartiennent.

Answer 4

Petit résumé de mon humble savoir:

Il existe quelques problèmes de calcul simples (comme trouver le chemin le plus court entre deux points d’un graphique), qui peuvent être calculés assez rapidement (O (n ^ k), où n est la taille de l’entrée et k est une constante (dans le cas des graphiques, c'est le nombre de sommets ou d'arêtes)).

D'autres problèmes, tels que trouver un chemin qui traverse tous les sommets d'un graphique ou obtenir la clé privée RSA à partir de la clé publique sont plus difficiles (O (e ^ n)).

Mais, selon CS, le problème est que nous ne pouvons pas "convertir" une machine de Turing non déterministe en une machine déterministe. Nous pouvons toutefois transformer des automates finis non déterministes (comme l'analyseur de regex) en automates déterministes ( eh bien, vous le pouvez, mais le temps d’exécution de la machine sera long). Autrement dit, nous devons essayer tous les chemins possibles (généralement, les professeurs CS intelligents peuvent en exclure quelques-uns).

C’est intéressant car personne n’a la moindre idée de la solution. Certains disent que c'est vrai, d'autres disent que c'est faux, mais il n'y a pas de consensus. Une autre chose intéressante est qu'une solution serait préjudiciable aux cryptages à clé publique / privée (comme RSA). Vous pouvez les casser aussi facilement que générer une clé RSA maintenant.

Et c'est un problème assez inspirant.

Answer 5

Il n’ya pas grand-chose que je puisse ajouter à la partie quoi et pourquoi de la partie P =? NP de la question, mais en ce qui concerne la preuve. Non seulement une preuve aurait-elle valu un crédit supplémentaire, mais elle résoudrait l'un des problèmes suivants: Problèmes du millénaire . Un sondage intéressant a récemment été mené et les résultats publiés (PDF) méritent d'être lus au sujet d'une preuve.

Answer 6

Tout d'abord, quelques définitions:

• Un problème particulier se pose dans P si vous pouvez calculer une solution en temps inférieur à n ^ k pour un certain k , où n est la taille de l'entrée. Par exemple, le tri peut être effectué dans n log n , lequel est inférieur à n ^ 2 . Le tri correspond donc au temps polynomial.

• Un problème existe dans NP s’il existe un k tel qu’il existe une solution de taille au plus n ^ k que vous puissiez vérifier à temps la plupart des n ^ k . Prenez 3 couleurs de graphiques: étant donné un graphique, une 3 couleurs est une liste de paires (sommets, couleurs) de taille O (n) et vous pouvez vérifier dans le temps O ( m) (ou O (n ^ 2) ) si tous les voisins ont des couleurs différentes. Un graphique ne peut donc être coloré que s'il existe une solution courte et facilement vérifiable.

Une définition équivalente de NP peut être résolue par une N machine de Turing déterministe en P temps olynomial ". Bien que cela vous indique d'où vient le nom, cela ne vous donne pas la même impression intuitive de la nature des problèmes de NP.

Notez que P est un sous-ensemble de NP: si vous pouvez trouver une solution en temps polynomial, il existe une solution qui peut être vérifiée en temps polynomial - il suffit de vérifier que la solution donnée est égale à celle que vous pouvez trouver.

Pourquoi la question P =? NP intéressant? Pour répondre à cette question, il faut d’abord voir quels sont les problèmes NP-complets. En termes simples,

• Un problème L est NP-complet si (1) L est dans P et (2) un algorithme qui résout L peut être utilisé pour résoudre tout problème L 'dans NP; c'est-à-dire, étant donné une instance de L ', vous pouvez créer une instance de L qui a une solution si et seulement si l'instance de L' a une solution. Formellement, chaque problème de NP est réductible à L.

Notez que l'instance de L doit être calculable en temps polynomial et avoir une taille polynomiale, de la taille de L '; Ainsi, résoudre un problème NP-complet en temps polynomial nous donne une solution en temps polynomial à tous tous les problèmes de NP.

Voici un exemple: supposons que nous sachions que la coloration en trois couleurs est un problème difficile à résoudre. Nous voulons prouver que décider de la satisfiabilité des formules booléennes est également un problème difficile à résoudre.

Pour chaque sommet v, avoir deux variables booléennes v_h et v_l et l'exigence (v_h ou v_l): chaque paire ne peut avoir que les valeurs {01, 10, 11}, que nous pouvons considérer comme étant la couleur 1, 2 et 3.

Pour chaque arête (u, v), exigez que (u_h, u_l)! = (v_h, v_l). C'est-à-dire

  

not ((u_h et non u_l) et (v_h et non v_l) ou ...)   énumérant toutes les configurations égales et stipulant qu’aucune d’entre elles n’est le cas.

AND , toutes ces contraintes donnent une formule booléenne de taille polynomiale ( O (n + m) ). Vous pouvez également vérifier que le temps de calcul est également polynomial: vous effectuez des opérations O (1) simples, par sommet et par arête.

Si vous pouvez résoudre la formule booléenne que j'ai créée, vous pouvez également résoudre la coloration des graphes: pour chaque paire de variables v_h et v_l, laissez la couleur de v être celle qui correspond aux valeurs de ces variables. En construisant la formule, les voisins n'auront pas les mêmes couleurs.

Par conséquent, si les graphes en 3 couleurs sont NP-complets, il en va de même pour la formule booléenne.

Nous savons que les graphiques en 3 couleurs sont NP-complets; Cependant, historiquement, nous en sommes venus à le savoir en montrant d'abord le caractère NP-complet de la satisfiabilité du circuit booléen, puis en le réduisant à la colorabilité 3 (au lieu de l'inverse).