Le 24 mai 2000, Clay Mathematics Institute a mis au point sept problèmes mathématiques, pour lesquels, la solution de l’un des problèmes gagnera une récompense de 1 000 000 for us pour le solveur. Connu sous le nom de problèmes du Millénaire, jusqu’à présent, un seul des sept problèmes est résolu jusqu’à ce jour.

vous voulez gagner un million de dollars, essayez d’en résoudre un de cette liste. Ce sont les problèmes énumérés pour une récompense d’un million de dollars.,

  1. Yang-Mills et écart de masse
  2. hypothèse de Riemann
  3. problème p vs NP
  4. équation de Navier–Stokes
  5. Conjecture de Hodge
  6. Conjecture de Poincaré
  7. conjecture de Birch et Swinnerton-Dyer

D’accord, soyons réalistes ici, ces problèmes sont ici pour une raison. Vous l’avez deviné, ces problèmes sont difficiles à résoudre. En fait, ils sont profonds et vraiment difficiles, pas seulement pour les résoudre, mais même pour comprendre l’énoncé du problème. La plupart des problèmes énumérés nécessiteront des connaissances et une analyse solides du sujet, même pour comprendre la question.,

La Conjecture de Poincaré est le seul problème résolu parmi ces sept questions. Ce problème provient du domaine de topologie, qui traite de la façon dont les objets s’emboîtent et de leur forme dans l’espace. Ce problème était spécifiquement lié aux sphères.

en 1904, le mathématicien français Henri Poincaré a demandé si la sphère tridimensionnelle était caractérisée comme l’unique collecteur à trois simplement connecté. Cette question, la conjecture de Poincaré, était un cas particulier de la conjecture de géométrisation de Thurston., La preuve de Perelman nous dit que chaque collecteur est construit à partir d’un ensemble de pièces standard, chacune avec l’une des huit géométries bien comprises.

Voir: https://www.claymath.org/millennium-problems

des choses Compliquées … uhmmm! Discutons un peu plus de cela avant de passer à P par rapport à NP.

Henri Poincaré, a déclaré le problème en 1904, qui en très général stipule que, si vous avez un objet sans trous et que sa taille est assez petite et finie, alors c’est une sphère (ou peut être transformée en sphère). Ce n’est pas seulement pour 3 dimensions mais pour toutes les dimensions.,

Mais la déclaration n’a pas été prouvée pour la quatrième dimension, Jusqu’à ce que Grigori Perelman ait trouvé la solution en 2003, basée sur les travaux de Richard Hamilton.

Si vous êtes intéressé, voici à quoi ressemble une solution à un million de dollars:https://arxiv.org/abs/math/0211159

Grigori Perelman a reçu un million de dollars et la médaille fields, qu’il a toutes deux refusées.

Que dire? Certains d’entre nous aime résoudre des problèmes, juste pour le plaisir de le résoudre.

le Bonheur est le plaisir!,

p versus NP est le problème le plus récent répertorié dans la liste des problèmes du Millénaire. Ce problème a été déclaré en 1971.

L’énoncé précis du problème P versus NP a été introduit en 1971 par Stephen Cook dans son article fondateur « the complexity of theorem proving procedures”.

pour comprendre correctement le problème P versus NP, une connaissance de base de la complexité informatique est indispensable. En fait, P vs NP est le problème le plus attendu pour la solution en informatique., Donc, une bonne compréhension de la façon dont ce problème affecte le paysage informatique nous aidera à digérer ce problème.

Si vous êtes nouveau sur le sujet de la complexité informatique ou de la complexité en général, je vous encouragerai fortement à jeter un coup d’œil à mon histoire précédente sur « Qu’est-ce que la complexité informatique?”

la Plupart des problèmes dans l’espace de calcul peut être réduit à un problème de décision. Cela signifie des problèmes où la réponse est oui ou non.

revenons donc à la question de ce qu’est P? et ce qui est NP?,

P et NP peuvent tous deux être considérés comme un ensemble de problèmes qui sont regroupés en fonction de la difficulté à résoudre et à évaluer la solution. Le terme difficile est particulièrement important dans ce contexte, ce qui signifie essentiellement que l’intensité informatique d’un problème est à résoudre et à vérifier la solution.

Par exemple, considérons le problème de la multiplication. C’est un problème relativement facile à résoudre. Non seulement que ce problème est facile à résoudre, cela peut également être vérifié avec la même facilité simplement en multipliant les nombres., Fondamentalement, tout problème qui peut être résolu en temps polynomial et dont le résultat peut être vérifié en temps polynomial, est sous l’ensemble de complexité de P.

p ( polynomial time) contient tous les problèmes de décision qui peuvent être résolus par une machine de Turing déterministe en utilisant une quantité polynomiale de temps

Il y a cet autre ensemble de problèmes qui peuvent être vérifiés en temps polynomial mais, pour résoudre ce problème, il faudra plus que du temps polynomial. Par exemple, prenons le Sudoku par exemple., Étant donné que nous avons une solution pour n’importe quel jeu, nous pouvons le vérifier facilement. Cela signifie que nous pouvons faire la partie Vérification en temps polynomial. Mais pour résoudre le puzzle, nous avons besoin de plus de temps. De plus, à mesure que le nombre de grilles augmente, la complexité de trouver une solution augmente de manière exponentielle.

NP (nondeterministic polynomial time) est une classe de complexité utilisée pour classer les problèmes de décision. NP est l’ensemble des problèmes de décision pour lesquels les instances de problème, où la réponse est « oui”, ont des preuves vérifiables en temps polynomial., (juste autorisés à être polynomialement grand, pas plus grand)

point Intéressant à noter est que chaque problème est dans P est une partie de NP. Mais cela pourrait ou non être l’étau-versa. Voici où l’état d’esprit de la recherche pitch-in. Donc, la solution aux problèmes NP est lente mais ils peuvent être vérifiés rapidement. Pouvons-nous améliorer la vitesse de la solution?

examinons le problème de primalité. Un test de primalité est un algorithme permettant de déterminer si un nombre d’entrée est premier.,

étant donné le nombre naturel n, n est-il premier?

ce problème était considéré comme un problème dans le sous-ensemble NP jusqu’à ce que le test de primalité AKS prouve que ce problème est sous P.,

le test de primalité AKS (également connu sous le nom de test de primalité Agrawal–Kayal–Saxena et test cyclotomique AKS) est un algorithme de primalité déterministe créé et publié par Manindra Agrawal, Neeraj Kayal et Nitin Saxena, informaticiens à L’Institut indien de technologie de Kanpur, le 6 août 2002, dans un article intitulé « 

alors, y a-t-il une possibilité que tous les problèmes de NP puissent être résolus en complexité P?, Ou y a-t-il un ensemble de problèmes qui seront toujours difficiles à trouver pour que P et NP restent toujours séparés? La réponse est inconnue. En fait, c’est le problème d’un million de dollars.

Si il est facile de vérifier qu’une solution à un problème est correct, est-il aussi facile de résoudre le problème?

typique des problèmes NP est celui du problème du chemin Hamiltonien: étant donné N villes à visiter, Comment peut-on faire cela sans visiter une ville deux fois? Si vous me donner une solution, je peux facilement vérifier qu’elle est correcte. Mais je ne peux pas trouver si facilement une solution.,

Voir: https://www.claymath.org/millennium-problems/p vs np-problème

Quelques problèmes dans NP peuvent être regroupées comme NP complet. Il s’agit d’un groupe de problèmes où si une solution rapide à l’un des problèmes est trouvée, nous pouvons résoudre facilement un groupe de problèmes dans le même ensemble de complexité.

un problème est NP-complet lorsqu’il peut être résolu par une classe restreinte d’algorithmes de recherche par force brute et qu’il peut être utilisé pour simuler tout autre problème avec un algorithme similaire.,

la complétude NP est particulièrement importante dans la discussion P versus NP en tant que solution en temps P, car un problème dans NP-complete set prouve que l’ensemble de complexité entier s’effondrera. Ce qui signifie que le NP-Complet = NP = P

Un problème NP-complet de problème dans NP et sera NP-Dur, ce qui signifie que ce problème est au moins aussi dur que n’importe quel problème dans NP, comme illustré ci-dessous.,

Un problème est NP-dur si un algorithme pour le résoudre peut être traduit en un pour résoudre un problème NP-problème (non déterministe polynomial en temps) problème. NP-hard signifie donc « au moins aussi dur que n’importe quel problème NP”, bien qu’il puisse, en fait, être plus difficile.

Il y a des problèmes en dehors de NP qui sont difficiles à faire une solution en même temps difficile à vérifier la solution, par exemple, considérons les échecs., Étant donné n’importe quelle position sur un tableau, il est difficile de trouver le meilleur mouvement suivant, il est également difficile de vérifier le prochain mouvement pour être précis ou non. Ce problème est en EXP (complexité temporelle exponentielle) et peut-être en dehors de NP.

la plupart des chercheurs dans le domaine de la théorie de la complexité computationnelle pensent que P n’est pas égal à NP. Événement bien qu’il existe de nombreux problèmes intéressants dans NP qui affectent notre vie d’aujourd’hui comme les problèmes d’optimisation. Une solution à un problème NP complet comme le repliement des protéines signifie que nous serons beaucoup plus proches de trouver le remède contre le cancer., De plus, si P=NP, alors nous pourrions trouver que la cryptographie à clé publique est cassée car elle dépend de la factorisation entière qui est un problème dans NP et nous dépendons de cette dureté pour la solution pour la plupart de notre cryptographie. Donc, les implications de prouver N=NP sont mélangées.

de nombreuses recherches ont été menées pour prouver P = NP ou l’étau-versa. Mais ce problème lui-même semble être NP-difficile (juste être sarcastique ici) car il n’y a pas de résultats concluants pour le moment. Mais le monde sera beaucoup plus intéressant si quelqu’un peut prouver que P=NP., Mais à partir de Maintenant, la plupart des gens bien éduqués sur le terrain pensent le contraire.

dans son blog, Scott Aaronson, célèbre chercheur en théorie de la complexité computationnelle, déclare que,

Si P = NP, alors le monde serait un endroit profondément différent de ce que nous supposons habituellement. Il n’y aurait aucune valeur particulière dans les « sauts créatifs”, aucun écart fondamental entre la résolution d’un problème et la reconnaissance de la solution une fois qu’elle est trouvée., Tous ceux qui pourraient apprécier une symphonie seraient Mozart; tous ceux qui pourraient suivre un argument étape par étape seraient Gauss; tous ceux qui pourraient reconnaître une bonne stratégie d’investissement seraient Warren Buffett.

Merci pour votre temps.

édité par Ashok Jeevan