human
N'importe lequel des sept problèmes du prix du millénaire Je viens de lire un article sur ces problèmes sur Wikipédia mais je n'y ai pratiquement rien compris. Quelqu'un peut-il expliquer l'un de ces problèmes dans un langage simple ? Surtout celui qui a été résolu. Merci . Explique comme si j'avais cinq ans.
gpt
* * P contre NP . * * Nous avons des problèmes. Nous voulons les résoudre. Nous ne voulons pas que cela prenne trop de temps. Nous sommes des gens occupés, après tout. ---- * I. Qu'est-ce que P ? * Voici un problème. Je vous donne une image et je vous demande de transformer en bleu chaque pixel rouge. Facile ! Vous descendez la ligne en demandant à chaque pixel, « hé mec, es-tu rouge ? » et, si c'est le cas, tu le rends bleu. Ce n'était pas si mal ! Si nous avions une grille n x n de pixels , cela ne nous aurait pris que n^2 étapes ! Ou , si vous voulez appeler demander et changer deux étapes différentes , cela nous a pris le double . OK peu importe . Nous sommes ici des informaticiens théoriques , nous ne nous soucions pas vraiment du coefficient . En fait , nous ne nous soucions même pas de l' exposant ! Cela nous a pris un temps * polynomial * , et c'est ce qui compte . Ce problème – le problème « transformer le rouge en bleu » – peut être résolu en temps polynomial, il se trouve donc dans la classe de complexité appelée P. Nous sommes très créatifs lorsqu'il s'agit de nommer les classes de complexité. P est la classe de complexité de * tous les problèmes qui peuvent être résolus en un temps polynomial. * Voici un autre problème en P. Disons que nous avons deux nombres et que nous voulons savoir quel est leur plus grand diviseur commun. En utilisant l'algorithme d'Euclide, nous pouvons en fait résoudre ce problème en un temps polynomial. ( Si vous ne savez pas ce qu'est l' algorithme d' Euclide , vous pouvez [ le vérifier sur Wikipedia ] ( URL_0 ) . Ou pas . Ce n'est pas si important pour cette explication . ) Donc si le plus grand des deux nombres est n , il prend un certain nombre de pas qui est un polynôme de la taille ( nombre de chiffres ) de n. En voici encore un autre, et c'est assez surprenant. Si vous avez un entier positif, et que vous voulez savoir s'il est premier, c'est aussi dans P ! Il existe une méthode de vérification qui ne prend qu'un nombre polynomial d'étapes. Si vous n'êtes pas convaincu que cela soit surprenant , notez que cela n'a été connu qu'en 2002 . ---- * II . Qu'est-ce que NP ? * D'accord, il semble qu'il y ait beaucoup de problèmes que nous pouvons résoudre en P. Qu'est-ce qu'il y a d'autre ? Voici un problème qui ne semble pas devoir se trouver dans P. Disons que vous voulez trouver mon mot de passe. Je suis une personne très secrète , mais je suis aussi assez sympathique alors je vous fais savoir que mon mot de passe se compose de huit lettres minuscules , et rien d' autre . Je vous donne également un endroit pour entrer autant de suppositions que vous le souhaitez et vous dire si c'était vrai ou non. [Remarque : Pour que ce soit un problème déterministe, vous devez théoriquement connaître tout ce qu'il y a à savoir sur la configuration, ce qui n'est pas le cas si un ordinateur vous dit par magie si vous aviez raison ou tort. Ignorez ceci à des fins d'explication ; Je vais vous parler d'un vrai problème de NP sous peu. ] Combien de temps vous faudra-t-il pour trouver mon mot de passe ? Tout au plus, il vous faudra 26 ^ 8 suppositions. Eh bien , c'est une exponentiation , n'est - ce pas ? Célébrons , nous sommes de nouveau en temps polynomial ! Euh - attendez. Non . La " taille " du problème était le 8 , pas le 26 . Il a donc fallu 26^n étapes , ce qui n'est décidément pas un polynôme . Zut . Voici cependant la chose intéressante : une fois que nous pensons avoir une réponse , il ne nous faut qu'un temps polynomial pour la vérifier ( à savoir , 1 étape ) ! Peu importe à quel point le problème a été difficile à résoudre, nous pouvons vérifier la solution très rapidement. Et c'est NP. Classe de problèmes vérifiables en temps polynomial. ( Il existe en fait un certain nombre de définitions équivalentes de NP qui ne semblent pas vraiment équivalentes mais qui le sont ; c'est juste la plus facile à comprendre . NP signifie temps polynomial non déterministe , qui consiste à utiliser une machine de Turing non déterministe pour résoudre le problème ... mais vous ne voulez pas en entendre parler . ) Ok , qu'y a - t - il d' autre dans NP ? Vous aimez les labyrinthes ? Parce que j'adore les labyrinthes ! Si je vous donne un labyrinthe (faisons-en un labyrinthe en 3D pour que vous ne vous plaigniez pas de la règle de la main droite), cela pourrait vous prendre énormément de temps pour trouver un chemin à travers. Mais , une fois que vous avez une solution ( sous la forme de quelque chose comme " avant , avant , droite , bas , bas , bas , ... " ) cela prendrait un temps polynomial pour vérifier que vous aviez raison . NP ! Quoi d'autre, quoi d'autre‽ Quelque chose appelé "SAT" est aussi dans NP. SAT vous donne quelque chose de ridicule comme ceci : ( ( A et B et pas C ) et ( pas A ou pas D ) ) et ( ( C ou D ) ou ( B et C et pas E ) ) Et vous demande s'il y a une affectation de vrai et de faux à chaque variable qui rend tout le gros gâchis vrai. Le résoudre semble être une énorme douleur, mais une fois qu'une solution vous est donnée, il ne devrait pas être trop difficile de faire un tas de va-et-vient pour voir si c'est bon. NP ! Beaucoup de choses sont NP. L'outil pot de peinture dans MS Paint est NP, car il doit faire le tour de la vérification de ce qui se trouve à côté de quoi. Il n'est pas évident que l'outil pot de peinture soit vérifiable en temps polynomial, mais croyez-moi, c'est en NP. Colorier des cartes pour que deux pays limitrophes n'obtiennent pas la même couleur est également dans NP . Le problème du voyageur de commerce est également dans NP (c'est le problème où vous devez vous arrêter une fois dans un tas de villes tout en parcourant le moins de distance possible). Encore une fois , croyez - moi que c'est dans NP . ---- *III. Donc quel est le problème ? * Quelque chose de drôle que nous aurions dû remarquer maintenant - tout dans P est aussi dans NP . Eh bien, duh. Si nous pouvons le résoudre en temps polynomial , nous pouvons également vérifier qu'il est résolu en temps polynomial . Donc quand on parle de choses dans NP , on veut dire des choses qui sont dans NP , mais pas aussi dans P , n'est - ce pas ? Euh ... eh bien ... D'accord . C'est un peu gênant. Nous ne savons pas vraiment s'il y a quelque chose dans NP qui n'est pas aussi dans P. J'ai dit que ce serait embarrassant ! Réfléchissons-y à nouveau. Nous ne savons pas s'il existe un seul problème concevable que nous puissions vérifier en temps polynomial et que nous ne puissions également résoudre en temps polynomial. Je vais vous donner une minute pour remonter dans votre fauteuil , remettre vos chaussettes et essuyer la boisson crachée de votre moniteur . Ce problème de pot de peinture , ces labyrinthes , ce truc bizarre de SAT , même le problème du voyageur de commerce . Ils ne semblent pas pouvoir être résolus en temps polynomial , n'est - ce pas ? Mais pouvez-vous le prouver ? Si vous le pouvez, le Clay Mathematics Institute vous doit 1 000 000 $. Ouais, c'est tout le problème. Pour voir s'il existe un seul problème dans NP qui n'est pas aussi dans P ( ce qui montrerait que P ≠ NP ) ou pour montrer que tout problème dans NP est aussi dans P ( ce qui montrerait que P = NP ) . Un sondage récent d'éminents informaticiens théoriques a montré que 61 % pensent P ≠ NP , 9 % pensent P = NP , 22 % n'ont pas d'opinion et 8 % pensent quelque chose d'un peu plus compliqué que je n'aborderai pas ici (mais si ça vous intéresse je peux élaborer ) . --- --- * * MATÉRIEL BONUS : NP - Complétude ! * * Il y a quelques problèmes dans NP dont nous avons magiquement prouvé qu'ils sont spéciaux d'une manière très étrange, et nous les appelons NP-complets. SAT, mentionné ci-dessus, est NP-complet. Cela signifie que chaque problème de NP - les labyrinthes, le problème du voyageur de commerce, etc. – peut être converti (en temps polynomial) en un problème en SAT, résolu en SAT, et reconverti. Peu importe la complexité du problème , nous pouvons l' encoder en A et en B et plusieurs millions d' alphabets supplémentaires , les enchaîner tous ensemble en and et en or selon un algorithme fou , et la solution au problème sera déterminée par la solution de SAT . Le problème du voyageur de commerce est également NP-complet. Oui, vous pouvez prendre n'importe quel problème NP et le transformer en une carte avec un tas de villes et un itinéraire proposé à travers elles, et la réponse oui / non au problème NP d'origine sera la même que si l'itinéraire proposé est le le plus court. Donc, si vous pouvez résoudre n'importe quel problème NP-complet en temps polynomial, tous les autres problèmes de NP peuvent être convertis en temps polynomial en ce problème, résolus en temps polynomial, puis reconvertis en temps polynomial. Additionnez trois polynômes pour obtenir un autre polynôme, et vous avez montré que P = NP. Donc , résolvez un problème NP - complet en temps polynomial , ou trouvez un seul problème NP qui ne peut pas être résolu en temps polynomial et de toute façon vous avez gagné un million de dollars . Pas une mauvaise façon de passer un après-midi. --- --- * * AVIS DE NON-RESPONSABILITÉ * * Ce qui précède fait un tas de choses qui ne sont pas rigoureuses du tout. Tous ces problèmes devraient avoir des solutions oui / non, un peu comme SAT, mais sont formulés d'une manière qui n'en a pas. Excuses .