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
P signifie " polnomial " . Un problème P est un problème qu'un ordinateur peut résoudre « rapidement », c'est-à-dire qu'il existe une limite particulière à la quantité de calculs que l'ordinateur doit effectuer pour résoudre le problème. NP signifie « polynôme non déterministe ». Cela signifie que l'ordinateur peut * vérifier * un résultat en temps polynomial, même s'il ne peut pas nécessairement trouver ce résultat à partir de zéro à une vitesse raisonnable. Pensez-y comme si vous faisiez un puzzle : si vous voulez faire un puzzle de 1 000 000 de pièces, cela vous prendra un certain temps. Si quelqu'un dit qu'il a résolu un puzzle de 1 000 000 de pièces, tout ce qu'il a à faire est de vous montrer l'image complète, ce qui prendra une seconde ou deux. De toute évidence, tous les problèmes P sont également NP, car si vous pouvez résoudre quelque chose à partir de zéro rapidement, vous pouvez simplement le faire pour le vérifier. La grande question est : Existe-t-il des problèmes NP qui ne sont pas aussi P ? ( Les ​​experts croient qu'il y en a , et ils sont presque sûrs qu'une classe particulière de problèmes NP appelés " problèmes NP - complets " ne sont pas P , mais ils n'en sont pas sûrs . )