human
Qu'est-ce que P vs NP ? Apparaît occasionnellement dans une conversation avec certains de mes amis nerds ; n'admettra jamais ne pas avoir la moindre idée de ce dont il parle . Explique comme si j'avais cinq ans.
gpt
Voici la version LI5. En informatique, certains problèmes sont considérés comme « faciles » et d'autres comme « difficiles ». Les problèmes simples peuvent être résolus rapidement. Les problèmes difficiles prennent beaucoup de temps à résoudre par un ordinateur. P est une classe de problèmes qui peuvent être résolus « rapidement ». Si l'entrée a une longueur de N bits , alors le problème peut être résolu en temps proportionnel à un polynôme de N. Comme N^2 . NP est une classe de problèmes qui peuvent être résolus lentement. Si l'entrée est longue de N bits , alors le problème peut être résolu en temps proportionnel à une exponentielle de N , comme 2^N. Maintenant , tout problème qui peut être résolu rapidement peut évidemment être résolu plus lentement , donc on dit que P est un sous - ensemble de NP . Maintenant , il se pourrait que tous les problèmes de NP -- tous ces problèmes lents et difficiles -- aient en fait une solution rapide . Si c'est le cas, nous dirions P = NP parce que tous les problèmes qui sont dans NP sont aussi dans P. Tous ces problèmes difficiles sont en fait assez faciles. Mais la plupart des gens pensent que P ! = NP - c'est-à-dire qu'il existe des problèmes "difficiles" pour lesquels il n'existe pas de solution rapide et facile. Cependant , découvrir si P = NP est le problème non résolu le plus célèbre en informatique .