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
Bon , et maintenant pour une vraie réponse ELI5 : " P " est le groupe de tous les problèmes qui sont faciles à résoudre . Et par là, nous voulons dire que le processus le plus connu pour le résoudre s'adapte bien au fur et à mesure que le problème s'agrandit. L'addition est facile - lorsque vous ajoutez des chiffres, vous n'ajoutez qu'une étape de plus (une colonne de plus à ajouter). Ainsi, lorsque les nombres à additionner deviennent mille fois plus grands, cela ne représente que 3 étapes de plus. Lorsque les chiffres deviennent un million de fois plus grands, cela ne représente que 6 étapes de plus. C'est vraiment une bonne mise à l'échelle. Si vous preniez le nombre d'atomes dans l'univers et le nombre de jeux d'échecs différents auxquels vous pouvez jouer, vous pourriez facilement les additionner à la main, si vous êtes rapide, peut-être en une minute environ. Un ordinateur pourrait le faire pratiquement instantanément. " NP " est le groupe de tous les problèmes qui peuvent ou non être faciles à résoudre , mais qui sont au moins faciles à vérifier . Si je vous donne 100 $ et que je vous dis d'aller à l'épicerie et de dépenser exactement autant d'argent (pour acheter n'importe quoi, cela n'a pas d'importance), comment faites-vous pour déterminer ce qu'il faut acheter ? quantité ? Nous ne connaissons pas une bonne façon d'aborder cela. Tout ce que vous pouvez vraiment faire est d'essayer des combinaisons de choses jusqu'à ce que vous la trouviez, ou d'essayer toutes les combinaisons et de constater que rien ne fonctionne. C'est assez difficile s'il n'y a que 10 articles, ça va être impossible dans un petit dépanneur, et ça va être super impossible dans une grande épicerie. Mais -- si je vous donne la solution ( " c'est 2 boites de Frosted Flakes , 3 boites de Spaghetti - Os , ... ) , c'est vraiment facile de vérifier que c'est correct , parce qu'il suffit d' ajouter et ajouter est facile. Notez que P est entièrement contenu dans NP - tout problème facile à résoudre est facile à vérifier, car vous pouvez le vérifier simplement en le résolvant à nouveau. Donc, le diagramme de Venn n'est pas le diagramme standard avec deux cercles qui se chevauchent , c'est une grosse bulle pour NP et une petite bulle pour P complètement à l' intérieur . P vs NP est la question de savoir si oui ou non ces deux groupes sont les mêmes . J'ai pris quelques problèmes NP et trouvé des solutions plus rapides, en les déplaçant dans P, donc les gens se sont demandés si peut-être tous les problèmes NP étaient aussi dans P. Nous soupçonnons vraiment que ce n'est pas le cas, mais personne n'a été capable de le prouver d'une manière ou un autre .