La question de savoir si P = NP est peut-être le plus célèbre dans l’ensemble de l’informatique. Ce que cela signifie ? Et pourquoi est-il si intéressant ?
Oh et pour un crédit supplémentaire, s’il vous plaît envoyer une preuve de la vérité ou la fausseté de la déclaration. :)
P désigne temps polynomial. NP est synonyme de non-déterministe polynomial en temps.
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. La complexité est le temps mesuré en nombre d'opérations qu'il allait prendre, en fonction du nombre d'éléments de données. Et une 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 existe deux types 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 vrai ordinateurs 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.
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, on peut 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 dans 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 existe 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 dans P, alors tous les NP problèmes sont révélés être en P). Si P = NP, alors tous ces problèmes vont être prouvé efficace (en 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 $1MM.
Pour 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 cela fonctionne 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 de la 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 difficile sorte de NP problème.
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.
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 finine automates (comme la regex parser) dans déterministe (eh bien, vous 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 interressant, 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. Un autre grand chose, c'est qu'une solution serait nocif pour les clés publique/privée encriptions (comme le RSA). Vous pouvait les briser aussi facilement que de générer une clé RSA est maintenant.
Et c'est une très inspirant problème.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
