human
Qu'est-ce que le problème P versus NP ? Wikipédia me fait mal au cerveau. Explique comme si j'avais cinq ans.
gpt
Les informaticiens aiment classer certains problèmes en fonction du temps qu'ils mettent à résoudre. Étant donné que le matériel peut varier en fonction des ordinateurs, nous ne comptons pas en secondes, mais plutôt en nombre d'opérations. De plus, si nous avons une grande expression compliquée, comme 3n'2 + n + 1, nous regardons simplement le terme qui domine à mesure que n augmente (n'2 dans ce cas) et nous ignorons le nombre devant lui. Nous appellerions donc cela O(n'2 ) , où O ( ) signifie essentiellement que nous faisons ceci . Il existe des définitions plus formelles qui ne sont plus si importantes aujourd'hui. ' désigne l' exponentiation , donc n'2 est n au carré Par exemple , si vous avez n nombres et que vous voulez trouver le minimum , en supposant que vous ne savez rien de l' ordre dans lequel ils vous sont donnés , vous pouvez résoudre ce problème en regardant chacun chose dans la liste et vérifier si elle est plus petite que la plus petite chose que vous avez vue jusqu'à présent. Cela signifie que ce problème peut être résolu en temps O(n ) , car on compte une unité de travail pour regarder chaque chose et il y a n choses . On dit qu'un problème est dans P s'il est O(n'k ) , où k est un nombre fixe . Donc n'1 , n'2 , n'100 sont tous dans P , mais 2'n et n'n ne le sont pas . Ici, le P signifie polynôme. Considérons maintenant un problème plus difficile. Disons que vous allez au restaurant et que des mois plus tard, vous savez exactement combien vous avez dépensé, mais pas ce que vous avez commandé (sans taxe ni pourboire). Vous voulez regarder le menu et comprendre cela. Une stratégie est d'essayer toutes les combinaisons de choses sur le menu et de voir ce qui correspond lorsque vous l'additionnez. Le fait est que s'il y a n choses sur le menu , il y a 2'n combinaisons possibles , ce qui signifierait que nous ne pouvons pas encore le classer comme P . Cela prendrait une éternité. Si le menu avait 16 éléments, vous devriez essayer environ 65 000 combinaisons. Nous voulons donc trouver un moyen plus efficace de le faire. Le problème est que personne n'a vraiment trouvé quoi que ce soit de sensiblement meilleur, ou quoi que ce soit dont le temps d'exécution tombe dans P. Mais, supposons que vous ayez en quelque sorte deviné ou rappelé ce que vous aviez. Ensuite, vous pourriez très rapidement additionner les chiffres et vérifier que vous aviez raison. Cela ne prendrait au maximum que le temps O(n ) pour tout additionner. Donc, vérifier quand vous connaissez déjà la réponse est super rapide et c'est en P. C'est NP. Un programme qui a de la chance et qui devine correctement ou qui a déjà un moyen secret de connaître la réponse peut la vérifier en temps polynomial. Mais nous ne savons pas si nous pouvons améliorer la stratégie pour arriver à cette supposition chanceuse autre que de simplement tout essayer. Cela fait une grande différence avec les ordinateurs , qui peuvent généralement résoudre rapidement les problèmes en P , mais nous considérons que les problèmes NP les plus difficiles sont trop difficiles à résoudre si nous ne connaissons pas déjà la réponse . Beaucoup de gens soupçonnent que P est différent de NP , mais nous ne savons pas . Si nous trouvions un moyen de résoudre ces problèmes en temps polynomial et en garantissant toujours que nous trouverons la bonne réponse sans chance ni connaissance préalable, alors nous serions en mesure de dire que P = NP.