Un exemple d'énigme complexe est le problème de P versus NP, qui est l'un des problèmes les plus célèbres et les plus importants en informatique théorique. Ce problème concerne la question de savoir si les problèmes de décision pour lesquels une solution peut être vérifiée rapidement peuvent également être résolus rapidement. En d'autres termes, est-ce que P = NP ? Si c'est le cas, cela signifie que les problèmes difficiles qui prennent actuellement des années à être résolus pourraient être résolus en quelques secondes. Cependant, malgré des décennies de recherche, personne n'a encore pu résoudre cette énigme de manière concluante? AIDEZ MOI SVPP JE COMPREND RIEN
More Questions From This User See All
Lista de comentários
Réponse :
Explications :
Je ne comprends pas la question que tu poses.
Pour ce qui est de la conjecture "P=NP ou P≠ NP" , je ne comprends pas qu'on vous en parle, c'est super difficile à comprendre quand on ne comprend pas "temps polynomial de calcul d'un algorithme" (ça, c'est le P).
Tu peux essayer de lire ce qui suit :
Il y a 7 énigmes à 1 million de dollars chacune, dont la démonstration de cette conjecture. C'est l'institut Clay qui propose cela.
Comment on présente le problème :
Est-ce que pouvoir vérifier rapidement une solution (trouvée on ne sait comment, ça c'est NP) à un problème implique de pouvoir la trouver rapidement (ça, c'est P) ?
Si on arrive à démontrer cela , c'est la fin du minage du bitcoin, c'est une révolution dans la crypto (je crois ce qu'on me dit !)
- l'exemple donné par l'institut Clay nous éclaire sur ce problème :
Supposons que vous soyez chargé de loger un groupe de quatre cents étudiants. 400, c'est crédible, dans une résidence universitaire.
Contrainte n°1 :
Le nombre de places est limité, seuls cent étudiants se verront attribuer une place dans la résidence universitaire.
Donc : une cominaison de 100 sur 400
Contrainte n°2 :
Le doyen vous a fourni une liste de paires d'étudiants incompatibles, et demande que deux étudiants d'une même paire ne puissent jamais apparaître dans votre choix final.
Ceci élimine certaines des combinaisons.
Ce problème est NP
En effet, il vous est facile de vérifier qu'une liste de cent étudiants fournie par un collègue est correcte, c'est-à-dire que les étudiants d'une même paire de la liste du doyen n'apparaissent jamais tous deux dans la liste de votre collègue.
Ce problème est-il P ?
Toutefois, produire une telle liste à partir de zéro paraît tellement difficile qu'elle en est même impraticable, car le nombre de façons de regrouper cent étudiants parmi quatre cents dépasse le nombre d'atomes de l'univers !
Pour cette raison, on ne peut même pas espérer construire un super-ordinateur capable de résoudre ce problème par force brute, c'est-à-dire en testant toutes les combinaisons de cent étudiants.
On insiste : est-ce que ce problème n'est pas P ?
Peut-être que cette apparente difficulté ne fait que refléter le manque d'ingéniosité de nos programmeurs.
Savoir s'il existe des problèmes dont la solution peut être vérifiée rapidement, mais qui requièrent un temps incroyablement long pour être résolus par un quelconque procédé, c'est ça l'énigme "P=NP ou P≠NP"