Ce qui est “P=NP?”, et pourquoi est-ce une célèbre question?

La question de savoir si P=NP est peut-être le plus célèbre dans l'ensemble de l'Informatique. Ça veut dire quoi? Et pourquoi est-il si intéressant?

Oh, et pour le crédit supplémentaire, merci de poster une preuve de la déclaration de la vérité ou de la fausseté. 🙂

Joliment aménagé par Scott Aaronson, MIT "Si P = NP, alors le monde serait très différent que celui que nous avons généralement supposer qu'il soit. Il n'y aurait aucune valeur particulière en "creative sauts," aucun écart fondamental entre la résolution d'un problème et la reconnaissance de la solution une fois qu'il est trouvé. Tous ceux qui peuvent apprécier une symphonie serait Mozart; tout le monde qui pourrait suivre une étape-par-étape argument serait de Gauss..." extrait de en.wikipedia.org/wiki/Complexity_classes_P_and_NP .
Voir aussi En termes de base, ce qui est la définition de P, NP, NP-Complet, et NP-Dur? sur Informatique.

OriginalL'auteur raldi | 2008-09-21

  1. 341

    P désigne temps polynomial. NP est synonyme de non-déterministe polynomial en temps.

    Définitions:

    • Temps Polynomial signifie que la complexité de l'algorithme est O(n^k), où n est la taille de vos données. g. nombre d'éléments dans une liste triée), et k est une constante.

    • Complexité est le temps mesuré en nombre d'opérations qu'il allait prendre, en fonction du nombre d'éléments de données.

    • Opération est tout ce qui fait sens comme une opération de base pour une tâche particulière. Pour le tri, le fonctionnement de base est une comparaison. Pour la multiplication de matrice de l'opération de base est la multiplication de deux nombres.

    Maintenant, la question est, qu'est-déterministes et non-déterministes veux dire. Il y a un résumé modèle de calcul, un ordinateur imaginaire appelé une machine de Turing (TM). Cette machine a un nombre fini d'états, et une infinité de bande, qui est discrète, les cellules dans lesquelles un ensemble fini de symboles peuvent être écrits et lus. À un moment donné, le TM est dans un de ses états, et il est à la recherche à une cellule en particulier sur la bande. En fonction de ce qu'il lit à partir de cette cellule, il peut écrire un nouveau symbole dans la cellule, déplacer la bande d'une cellule vers l'avant ou vers l'arrière, et aller dans un autre état. Ceci est appelé un état de transition. Assez étonnamment, par attentivement la construction d'états et de transitions, vous pouvez concevoir un TM, ce qui est équivalent à un programme d'ordinateur qui peut être écrit. C'est pourquoi il est utilisé comme un modèle théorique pour prouver des choses sur ce que les ordinateurs peuvent faire et ne pas faire.

    Il y a deux sortes de TM qui nous concernent ici: déterministe et non déterministe. Un déterministe TM a une seule transition de chaque état pour chaque symbole qu'il est la lecture de la bande. Un non-déterministe TM peut avoir plusieurs de ces de transition, j'. e. il est en mesure de vérifier plusieurs possibilités simultanément. C'est un peu comme la ponte de plusieurs threads. La différence est qu'un non-déterministe TM peuvent apparaître comme beaucoup de ces "fils", comme il veut, alors que sur un ordinateur réel uniquement un nombre de threads peut être exécutée à un moment (égal au nombre de Processeurs). En réalité, les ordinateurs sont fondamentalement déterministe TMs fini avec des bandes. D'autre part, un non-déterministe TM ne peut pas être physiquement réalisé, sauf peut-être avec un ordinateur quantique.

    Il a été prouvé que tout problème qui peut être résolu par un non-déterministe TM peut être résolu par un déterministe TM. Cependant, il n'est pas clair combien de temps cela va prendre. La déclaration de P=NP signifie que si un problème a temps polynomial non-déterministe TM, alors on peut construire un déterministe TM qui permettrait de résoudre le même problème en temps polynomial. Jusqu'à présent personne n'ont été en mesure de montrer qu'il peut être fait, mais personne n'a été en mesure de prouver qu'il ne peut pas être fait, soit.

    NP-complets problème un problème NP X, de telle sorte que tout problème NP Y peut être réduite à X par un polynôme de réduction. Cela implique que si jamais quelqu'un arrive avec un polynôme en temps de la solution à un problème NP-complet de problème, qui va également donner un polynôme solution à tout problème NP. Ainsi que tendrait à prouver que P=NP. A l'inverse, si quelqu'un devait prouver que P!=NP, nous pouvons être certains qu'il n'y a aucun moyen de résoudre un problème NP en temps polynomial sur un ordinateur classique.

    Un exemple d'une NP-complets problème est le problème de trouver une vérité affectation qui ferait une expression booléenne contenant n variables vrai.

    Pour le moment, dans la pratique, n'importe quel problème qui prend un temps polynomial non-déterministe TM ne peut être fait en temps exponentiel sur un déterministe TM ou sur un ordinateur classique.

    Par exemple, la seule façon de résoudre la vérité d'affectation problème est d'essayer de 2^n possibilités.

    Ce n'est pas vrai que la seule façon de résoudre SAT est énumération des cas. Voir en.wikipedia.org/wiki/... pour des informations sur l'algorithme DPLL, qui est en fait très efficace dans de nombreux cas.
    Derek, je me permets d'être en désaccord. Je ne vois vraiment pas comment vous expliquer P et NP sans machines de Turing. J'ai été une fois dans un des algorithmes de la classe, qui a essayé. Si je ne savais pas sur TM, je serais totalement perdu.
    C'est vrai en pratique que la résolution d'un problème NP-complet problèmes prend plus de temps polynomial sur une machine réelle, mais ce n'est pas ce que cela signifie, c'est juste de l'état actuel de l'art, comme une conséquence du fait que P=NP est inconnue. Si quelqu'un a trouvé un algorithme polynomial pour résoudre tout problème NP-complet de problème, qui prouveraient que P=NP, et nous savons que cela n'est pas arrivé parce qu'il serait dans l'actualité! A l'inverse si il a été prouvé que P!=NP, alors nous pouvons dire avec confiance que pas de NP-complets problème est résoluble en temps polynomial.
    Je sais que c'est assez vieux, mais je veux juste dire que la réponse est épique et c'est le premier qui ont cliqué pour moi ! Bon travail
    Correction dans l'avant dernier paragraphe: "nous voulons être certains qu'il n'y a aucun moyen de résoudre un NP Complet problème en temps polynomial sur un ordinateur classique", puisque P est un sous-ensemble de NP, et à prouver que P != NP ne veut pas nécessairement dire quelque chose à propos de ce que les problèmes dans NP qui ne sont pas NP-Complet sont en fait dans P.

    OriginalL'auteur Dima

  2. 79
    1. Un oui ou non le problème est dans P (Polynomial temps) si la réponse peut être calculée en temps polynomial.
    2. Un oui ou non le problème est dans NP (Nsur-déterministe Polynomial temps) si une réponse oui peut être vérifié en temps polynomial.

    Intuitivement, nous pouvons voir que, si un problème est dans P, alors il est dans NP. Donné une réponse potentielle à un problème dans P, nous pouvons vérifier la réponse simplement en recalculant la réponse.

    Moins évident, et beaucoup plus difficile à répondre, est de savoir si tous les problèmes de NP sont en P. Le fait que l'on peut vérifier une réponse en temps polynomial dire que l'on peut calculer la réponse en temps polynomial?

    Il y a un grand nombre de problèmes importants qui sont connus pour être NP-complet (en gros, si tous ces problèmes sont révélés être en P, puis tous NP problèmes sont révélés être en P). Si P = NP, tous ces problèmes seront prouvé efficace (temps polynomial) solution.

    La plupart des scientifiques estiment que P!=NP. Toutefois, aucune preuve n'a encore été établi, soit P = NP ou P!=NP. Si quelqu'un fournit une preuve, soit conjecture, ils vont gagner 1 million de dollars US.

    OriginalL'auteur Derek Park

  3. 23

    De donner la réponse la plus simple je pense:

    Supposons que nous avons un problème qui prend un certain nombre d'entrées, et a différentes solutions possibles, ce qui peut ou peut ne pas résoudre le problème pour les entrées données. Un puzzle de logique dans un puzzle magazine serait un bon exemple: les entrées sont les conditions ("George ne vit pas dans le bleu ou le vert de la maison"), et le potentiel de la solution est une liste de déclarations ("George vit dans la maison jaune, pousse de pois, et le propriétaire du chien"). Un exemple célèbre est le problème du voyageur de commerce: étant donné une liste de villes, et à la fois pour l'obtenir à partir de n'importe quelle ville à une autre, et une limite de temps, une solution possible serait une liste de villes dans l'ordre le vendeur visites, et il pourrait fonctionner si la somme des temps de déplacement est inférieure à la limite de temps.

    Un tel problème est dans NP si nous pouvons contrôler efficacement une solution potentielle pour voir si elle fonctionne. Par exemple, étant donné une liste des villes pour le vendeur à visiter dans l'ordre, nous pouvons ajouter les temps pour chaque trajet entre les villes, et de voir facilement si c'est sous la limite de temps. Un problème est dans P si l'on peut effectivement trouver une solution s'il en existe un.

    (De façon efficace, ici, a un sens mathématique précis. Pratiquement, cela signifie que les grands problèmes ne sont pas excessivement difficile à résoudre. Lors de la recherche d'une solution possible, un moyen inefficace serait à la liste de tous les possibles solutions possibles, ou quelque chose d'approchant que, tout d'un moyen efficace nécessiterait la recherche d'un beaucoup plus limité.)

    Par conséquent, le P=NP problème peut être exprimé de cette façon: Si vous pouvez le vérifier une solution à un problème du type décrit ci-dessus de manière efficace, pouvez-vous trouver une solution (ou prouver il n'y a aucun) de manière efficace? La réponse évidente est "Pourquoi devriez-vous être en mesure de le faire?" et c'est à peu près là où l'affaire se trouve aujourd'hui. Personne n'a été en mesure de le prouver d'une façon ou d'une autre, et qui dérange beaucoup de mathématiciens et d'informaticiens. C'est pourquoi toute personne qui peut prouver que la solution est en place pour un million de dollars de la Claypool Fondation.

    En général, nous supposons que P n'est pas égal à NP, qu'il n'existe aucune façon de trouver des solutions. Si il s'est avéré que P=NP, beaucoup de choses allaient changer. Par exemple, la cryptographie deviendrait impossible, et avec elle, toute sorte de vie privée ou de la vérifiabilité sur Internet. Après tout, nous pouvons efficacement prendre le texte chiffré et la clé et de produire le texte original, donc si P=NP, nous pourrions efficace de trouver la clé sans le savoir à l'avance. Craquage de mot de passe qui allait devenir trivial. D'autre part, il y a des classes entières de problèmes de planification et d'allocation des ressources aux problèmes qu'on peut résoudre efficacement.

    Vous avez peut-être entendu la description NP-complet. Un NP-complets problème est NP (bien sûr), et a cette propriété intéressante: si c'est dans P, chaque NP problème est, et si P=NP. Si vous pouviez trouver un moyen de résoudre efficacement le problème du voyageur de commerce, ou des puzzles de logique de puzzle, des magazines, vous pouvez résoudre efficacement tout en NP. Un NP-complets problème est, en un sens, le plus dur genre de problème NP.

    Donc, si vous pouvez trouver un général efficace solution technique pour tout problème NP-complet de problème, ou de prouver qu'il n'en existe, la gloire et la fortune sont les vôtres.

    Dans votre avant-dernier paragraphe, vous avez "en un sens, le plus difficile de tri". Il faut vous dire, NP-complets sont les plus difficiles car ils sont NP-dur.
    Je ne suis pas sûr que la fortune serait la vôtre. Le gouvernement pourrait vouloir de votre tête.

    OriginalL'auteur David Thornley

  4. 9

    Un court résumé de mon humble connaissance:

    Il y a quelques problèmes informatiques (comme trouver le chemin le plus court entre deux points dans un graphique), qui peut être calculée de façon assez rapide ( O(n^k), où n est la taille de l'entrée et k est une constante (dans le cas des graphes, c'est le nombre de sommets ou les arêtes).

    D'autres problèmes, comme de trouver un chemin qui traverse chaque sommet d'un graphe ou d'obtenir la clé privée RSA à partir de la clé publique est plus difficile (O(e^n)).

    Mais CS parler dit que le problème est que nous ne pouvons pas "convertir" un non-déterministe de Turing-machine déterministe, nous pouvons, toutefois, de transformer non-déterministe automates finis (comme la regex parser) dans déterministe (le bien, vous le pouvez, mais le moment de l'exécution de la machine va prendre longtemps). C'est, nous devons essayer tous les chemins possibles (généralement smart CS professeurs peuvent exclure quelques-uns).

    C'est intéressant parce que personne n'a même aucune idée de la solution. Certains disent que c'est vrai, certains disent que c'est faux, mais il n'y a pas de consensus. Une autre chose intéressante est qu'une solution serait dangereux pour publique/clé privée de chiffrement (comme le RSA). Vous pouvait les briser aussi facilement que de générer une clé RSA est maintenant.

    Et c'est assez inspirant problème.

    Ce n'est pas tout à fait vrai - vous pouvez convertir un NDTM à un DTM, mais la nouvelle machine dispose d'un temps d'exécution exponentiel dans le temps d'exécution de l'original (vous efficacement la largeur de recherche, la transition de l'état graphique de la NDTM).
    Ok, je vais mettre à jour la réponse.

    OriginalL'auteur terminus

  5. 6

    Il n'y a pas beaucoup que je peux ajouter pour le quoi et le pourquoi de la P=?NP partie de la question, mais en ce qui concerne la preuve. Non seulement une preuve d'une valeur de crédit supplémentaire, mais il permettrait de résoudre l'un des Problèmes Du Millénaire. Un intéressant sondage a été effectué récemment et la les résultats publiés (PDF) sont certainement la peine de lire en ce qui concerne l'objet de la preuve.

    OriginalL'auteur rjzii

  6. 5

    D'abord, quelques définitions:

    • Un problème particulier est dans P si vous pouvez calculer une solution en temps de moins de n^k pour certains k, où n est la taille de l'entrée. Par exemple, le tri peut être fait dans n log n qui est à moins de n^2, de sorte que le tri est temps polynomial.

    • Un problème est dans NP s'il existe un k telle qu'il existe une solution de la taille de la plupart des n^k ce que vous pouvez vérifier en temps au plus n^k. Prendre 3-coloration des graphes: étant donné un graphe, une 3-coloration est une liste de (vertex, couleur) des paires, qui a la 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. Si un graphe est 3-colorable seulement si il est court et facilement vérifiables solution.

    Un équivalent définition de NP est "les problèmes résolubles par un Nondeterministic machine de Turing dans Polynomial temps". Tout qui vous indique où le nom vient de la, il ne vous donne pas la même sensation intuitive de ce que NP problèmes sont comme.

    Remarque 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é en temps polynomial--il suffit de vérifier que la solution donnée est égal à celui que vous pouvez trouver.

    Pourquoi la question P =? NP intéressant? Pour répondre à cela, on doit d'abord voir ce que NP-complet problèmes. Mis simplement,

    • Un problème de L est NP-complet si (1) L est dans P, et (2) un algorithme qui résout L peut être utilisé pour résoudre n'importe quel problème de L' NP; que, compte tenu d'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 parlant, chaque problème de L' NP est réductible à L.

    Noter que l'instance de L doit être polynomiale en temps calculable et ont polynomiale de la taille, de la taille de L'; de cette manière, la résolution d'un problème NP-complet de problème en temps polynomial nous donne un temps polynomial une solution à tous NP problèmes.

    Voici un exemple: supposons que nous savons que la 3-coloration des graphes est un problème NP-difficile. Nous voulons prouver que la décision de la satisfiabilité des formules booléennes est un problème NP-difficile ainsi.

    Pour chaque sommet v, deux variables booléennes v_h et v_l, et de l'exigence (v_h ou v_l): chaque paire ne peut avoir d'autres valeurs {01, 10, 11}, que l'on peut penser que la couleur 1, 2 et 3.

    Pour chaque arête (u, v), l'exigence que (u_h, u_l) != (v_h, v_l). C'est,

    not ((u_h and not u_l) and (v_h and not v_l) or ...)
    l'énumération de tous l'égalité des configurations et de la stipulation qu'aucun d'entre eux est le cas.

    AND'ing ensemble toutes ces contraintes donne une formule booléenne qui a polynomiale de la taille (O(n+m)). Vous pouvez vérifier que cela prend un temps polynomial pour calculer ainsi: vous êtes en train de faire simple O(1) choses par un sommet et par le bord.

    Si vous pouvez résoudre la formule booléenne que j'ai fait, alors vous pouvez aussi résoudre graphique coloriage: pour chaque paire de variables v_h et v_l, laissez la couleur de v être celui correspondant à la valeur de ces variables. Par la construction de la formule, les voisins n'aurez pas l'égalité de couleurs.

    Ainsi, si la 3-coloration des graphes est NP-complet, donc est de type boolean-formule-satisfiabilité.

    Nous savons que la 3-coloration des graphes est NP-complet; cependant, historiquement, nous savons que par la première apparition de la NP-complétude de boolean-circuit-satisfiabilité, puis réduire à 3 colorability (au lieu de l'inverse).

    OriginalL'auteur Jonas Kölker