human
Qu'est-ce que P vs NP et comment une solution pourrait-elle bénéficier à l'informatique ? ELI5 : Qu'est-ce que P vs NP et comment une solution pourrait-elle bénéficier à l'informatique ? S'il vous plaît, expliquez-moi comme si j'avais cinq ans.
gpt
Réponse courte : les problèmes dans NP sont « plus difficiles » que les problèmes dans P. Si l'on pouvait prouver que P = NP, cela voudrait dire que tous les problèmes qui sont actuellement dans NP mais pas dans P ont une solution plus rapide. Cela ne vous donnerait pas cette solution , mais cela vous dirait qu'il y en a une . Toutes les réponses jusqu'ici sont fausses, d'une manière subtile ou d'une autre, donc je vais entrer dans plus de détails. * * Edit : * * il s'est avéré qu'il y avait aussi une erreur dans mon explication :-) J'ai utilisé à l'origine le problème du voyageur de commerce comme exemple, mais c'était incorrect car ce n'est pas NP-complet. En utilisant la somme du sous-ensemble maintenant. En informatique, les problèmes sont parfois divisés en "classes". La classe P comprend tous les problèmes qui peuvent être résolus en temps polynomial par un algorithme déterministe. "Temps polynomial" signifie que compte tenu de la taille du problème N (par exemple, trier N nombres du plus petit au plus grand), il peut être résolu en temps proportionnel à N^k, où k est une constante (qui peut être grande). « Algorithme déterministe » signifie qu'il peut être résolu par un algorithme de manière constructive, c'est-à-dire qu'il existe un algorithme qui peut prendre l'entrée, faire les choses de manière déterministe (c'est-à-dire simplement en regardant l'entrée et sans aide extérieure) et arriver à un Solution . Par exemple , le tri de N nombres peut être fait en N*log(N ) temps , qui est inférieur à N^2 , donc le tri est en P. Un exemple de problème qui n'est pas * actuellement * en P est le " sous-ensemble somme" problème : étant donné un ensemble de N entiers, par exemple {-5, 3, 2, 7}, existe-t-il un sous-ensemble de l'ensemble dont la somme est 0 ? ( Dans l' exemple , ce serait { -5 , 3 , 2 } ) . Je dis * actuellement dans NP * parce que ce n'est pas parce que personne n'a trouvé d'algorithme polynomial pour résoudre ce problème que cela ne peut pas être fait. En fait , si on pouvait prouver que ceci ne peut pas être résolu dans P , ce serait une preuve de P ! = NP ( plus à ce sujet plus tard ) . La classe NP comprend tous les problèmes qui peuvent être résolus en temps polynomial par un algorithme * non * déterministe . C'est fantaisiste de dire qu'il peut être résolu en N^k si vous connaissez déjà la solution, ce qui est une autre façon de dire qu'une fois que vous avez la solution, vous pouvez vérifier qu'elle est bien correcte en temps polynomial N^k . Par exemple, le problème de la somme des sous-ensembles tombe dans NP. Cela signifie que si quelqu'un vous donne un sous-ensemble de somme 0 , vous pouvez vérifier en temps N^k qu'il s'agit d'un sous-ensemble correct. Dans le cas d' une somme de sous - ensembles , la vérification est en fait triviale -- additionnez simplement les nombres et voyez si le résultat est 0 . Puisque tous les problèmes qui peuvent être résolus en temps polynomial peuvent aussi être vérifiés en temps polynomial (en les résolvant à nouveau), il est facile de voir que tous les problèmes de P sont aussi dans NP. Donc si vous pouviez prouver que la somme des sous-ensembles ne peut pas être résolue en P (ce qui n'est actuellement pas prouvé), et parce que nous savons qu'elle peut être vérifiée en temps polynomial, cela signifierait que P ! = NP . La preuve P = NP signifierait que tous les problèmes qui peuvent être vérifiés en temps polynomial ont aussi une solution en temps polynomial . Cela en soi ne résoudrait vraiment rien , mais cela garantirait que tous les problèmes qui peuvent actuellement être vérifiés , mais non résolus en temps polynomial , ont également une solution en temps polynomial . La preuve P !=NP serait moins utile -- elle prouverait que certains des problèmes qui sont actuellement dans NP mais pas dans P ne peuvent pas être résolus en temps polynomial , mais il pourrait encore y en avoir certains qui le peuvent .