Cet article est apparu à l’origine sur Motherboard Germany. Depuis sa publication originale, il a été mis à jour avec de nouvelles informations par Motherboard US. Qu’est-ce que le cancer curable, le capitalisme équitable et le jeu parfait de Super Mario Bros. ont tous en commun? Par une théorie mathématique, la solution à l’un des ces problèmes nous permettrait de résoudre rapidement les autres., Il suffit de meilleurs algorithmes pour prouver que des questions compliquées-telles que le repliement des protéines, les marchés efficaces et les analyses combinatoires—ne sont que des variations de problèmes plus simples que les supercalculateurs sont déjà capables de résoudre. Mais comment un algorithme peut-il simplifier des problèmes extrêmement compliqués? Cela dépend d’une autre question: et si les problèmes compliqués ne sont en réalité que de simples problèmes déguisés?, Cette énigme reste l’une des plus grandes questions non résolues des mathématiques modernes, et est l’un des sept problèmes du prix du Millénaire, pour lequel chaque réponse acceptée est récompensée par un million de dollars.
Maintenant, un homme allemand nommé Norbert Blum a affirmé avoir résolu le au-dessus de l’énigme, qui est bien connu comme le P vs NP problème. Malheureusement, sa prétendue solution ne porte pas de bonnes nouvelles., Blum, qui est de l’Université de Bonn, affirme dans son article de 38 pages récemment publié que P n’est pas égal à NP. En d’autres termes, les problèmes compliqués sont fondamentalement différents des problèmes simples et il ne semble pas que nos ordinateurs haute performance seront en mesure de résoudre ces problèmes les plus difficiles à tout moment dans un proche avenir. Et dans les jours qui ont suivi la publication de son article, de nombreux mathématiciens ont commencé à se demander si Blum l’avait résolu.
Quel est exactement le problème P versus NP?,
la plupart des informaticiens ont tendance à être d’accord avec la conclusion de Blum. Les problèmes difficiles sont difficiles, les problèmes faciles sont faciles. En informatique, les problèmes faciles tombent généralement sous la bannière de P. cela signifie qu’ils peuvent être résolus en « temps polynomial », ce qui revient à dire qu’ils peuvent être résolus dans un délai raisonnable. Beaucoup plus difficiles sont les problèmes NP, que les ordinateurs sont incapables de résoudre dans un délai raisonnable. À des fins pratiques, les problèmes NP pourraient aussi bien être insolubles par les ordinateurs., (Notez cependant que NP signifie « temps polynomial non déterministe » plutôt que « temps non polynomial ».) Voici quelques exemples de problèmes NP:
repliement des protéines: processus par lequel les protéines d’un organisme biologique obtiennent leur structure. Une meilleure compréhension de ce processus pourrait nous aider à reconnaître ou même à entraver les mutations, qui pourraient guérir certaines formes de cancer. Optimized routefinding: un itinéraire de voyage optimisé à travers 15 villes différentes sans visiter la même ville deux fois?, Un écrou dur à craquer, même pour un supercalculateur, c’est pourquoi cela est également considéré comme un problème NP en informatique.
Le parfait jeu d’échecs: Un jeu d’échecs possède une infinité de coups possibles, de telle sorte que même un supercalculateur avec une incroyable capacité ne peut pas déterminer une tactique parfaite. De nombreux mathématiciens considèrent ce problème si difficile qu’ils ne le considèrent pas comme un problème NP, mais le considèrent plutôt complètement hors du domaine des possibilités.,
Tous ces problèmes complexes ont une chose en commun: aussi difficile soit-il de trouver une solution aux problèmes NP, il est relativement facile de vérifier la validité des solutions Une fois que vous les avez.
Ces deux distinctions catégoriques dans la complexité des problèmes ont leurs origines avant l’essor sociétal des ordinateurs personnels. Dans les années 1970, lorsque les ordinateurs avaient encore la taille d’un réfrigérateur maladroit, il a été rapidement déterminé que tous les problèmes de l’humanité ne pouvaient pas être simplement résolus par ces machines., Il a été proposé que la distinction puisse être formalisée en termes de complexité de calcul, conduisant à une suite de classes de complexité, y compris N et NP.
Depuis La définition formelle de P et NP en 1971, les informaticiens ont débattu de la possibilité ou non de trouver un algorithme capable de réduire ou de redéfinir les problèmes NP de sorte qu’ils puissent être résolus en temps polynomial. Si quelqu’un était capable de prouver que tous les problèmes NP ne sont finalement que des variations de problèmes P, alors tous les problèmes NP seraient essentiellement soumis à la même forme de réduction., En d’autres termes, quiconque connaît la tactique parfaite de Super Mario Bros.pourrait également guérir le cancer.
au total, 116 des plus courageux dans leur domaine ont officiellement tenté de résoudre ce mystère (bien qu’un nombre incalculable d’informaticiens aient publié des solutions potentielles sur des tableaux de messages et sur des sites comme arXiv). À ce jour, aucune de ces preuves n’a été officiellement reconnue par la communauté des mathématiques.
une sorte de qui veut être millionnaire?, pour les mathématiciens
en 2000, Le Clay Mathematics Institute (CMI), situé à Oxford, a compilé une liste de sept problèmes non résolus du prix du Millénaire, promettant un million de dollars pour chaque solution. C’est une sorte de qui veut être millionnaire? ou X prix pour les mathématiciens. Les problèmes du prix du Millénaire sont considérés comme exceptionnellement difficiles, même dans les cercles d’experts. Une richesse de connaissances spécifiques au domaine est nécessaire pour comprendre les questions., Le seul problème du prix du Millénaire résolu à ce jour est la conjecture de Poincaré, qui n’est pas facilement expliquée en aparté dans un article sur un concept mathématique différent.
résoudre le problème NP ne serait pas une bonne chose. Par exemple, la plupart des chiffrements sont basés sur la difficulté de factoriser de très grands nombres premiers. La factorisation d’entiers est un problème de classe NP. Un code de 256 bits, comme ceux que les institutions financières utilisent dans les paiements par carte de crédit en ligne, est considéré comme incassable, et donc très sûr., Si QUELQU’un prouve que NP est égal à P, les banques devraient rapidement trouver une méthode de sécurité différente.
Que pensent les mathématiciens de la preuve mathématique de Blum?
Depuis la publication de L’article de Blum, les mathématiciens et les informaticiens du monde entier se demandent si le chercheur basé à Bonn a, en fait, résolu ce problème du prix du Millénaire. Après une réaction initialement positive, comme celle du mathématicien de Stanford Reza Zadeh, des doutes commencent à surgir quant à savoir si le raisonnement de Blum est correct.,
Dans un forum de mathématiques théoriques, un utilisateur nommé Mikhail a contacté Alexander Razborov—l’auteur de L’article sur lequel est basée la preuve de Blum—pour lui poser des questions sur L’article de Blum. Razborov prétend avoir découvert une erreur dans L’article de Blum: l’argument principal de Blum contredit l’une des hypothèses clés de Razborov. Et le mathématicien Scott Aaronson, qui est en quelque sorte une autorité dans la communauté mathématique en ce qui concerne P vs., NP, a dit qu’il serait prêt à parier $200,000 que la preuve mathématique de Blum ne durera pas. « S’il vous plait, arrêtez de demander », écrit Aaronson. Si la preuve n’a pas été réfutée, « vous pouvez revenir et me dire que j’étais un imbécile fermé d’esprit. »Dans la semaine qui a suivi le premier billet de blog D’Aaronson, d’autres mathématiciens ont commencé à essayer de percer des trous dans la preuve de Blum. Dick Lipton, professeur d’informatique à Georgia Tech, a écrit dans un article de blog que la preuve de Blum « passe de nombreux filtres de gravité », mais a suggéré qu’il pourrait y avoir des problèmes avec elle., Un commentateur de ce blog, connu uniquement sous le nom de « vloodin », a noté qu’il y avait une « seule erreur sur un point subtil » dans la preuve; d’autres mathématiciens ont depuis sonné et confirmé l’analyse initiale de vloodin, et donc le consensus émergent parmi de nombreux mathématiciens est qu’une solution pour P vs NP reste insaisissable. Traduit par Melina McCormack.