Les collections

P vs NP, NP-Complete et un algorithme pour tout

P vs NP, NP-Complete et un algorithme pour tout


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Il s'agit du sixième article d'une série en sept parties sur les algorithmes et le calcul, qui explore comment nous utilisons des nombres binaires simples pour alimenter notre monde. Le premier article, Comment les algorithmes gèrent le monde dans lequel nous vivons, peut être trouvé ici.

Lorsque nous nous asseyons pour essayer de résoudre un problème, très peu d’entre nous essaient de déterminer le type de problème que nous essayons de résoudre. Dans presque tous les cas, la réponse à cette question est un exercice intéressant et peut même vous aider à résoudre le problème dans certains cas, mais pas grand-chose d'autre. Mais la situation est très différente avec quelque chose comme le problème du voyageur de commerce, c'est pourquoi c'est un tel sujet d'étude et de recherche par des informaticiens théoriciens et des mathématiciens. Il a tout à voir avec sa classification comme problème.

Problèmes de classification: P Vs NP

Les problèmes pour lesquels nous connaissons un algorithme efficace qui est capable de produire une solution en temps polynomial sont classés comme Problèmes PP veux dire Temps polynomial, dans ce cas. C'était évidemment le premier sous-ensemble de problèmes que nous avons pu classer: de tous ces problèmes là-bas, au moins nous avons réussi à les résoudre ici. Des choses comme le tri des listes, l'équilibrage des arbres, le chiffrement des données sont tous des problèmes pour lesquels nous avons des algorithmes efficaces et appartiennent donc au sous-ensemble. P.

Plus tard, nous avons découvert un autre sous-ensemble de problèmes qui P lui-même était un sous-ensemble de, Problèmes de NP. le NP signifie temps polynomial non déterministe, mais pour nos besoins, vous n’avez pas besoin d’en savoir trop sur ce que cela signifie, sauf que cela fait partie de l’informatique fondamentale de l’ère de Turing qui sous-tend chaque ordinateur moderne. Ce que vous devez savoir, c'est que Problèmes de NP n'ont pas d'algorithme connu pouvant produire un résultat en temps polynomial.

Cependant, si vous avez une solution à un Problème NP, vérifier qu'il est correct est facile et peut être fait en Temps polynomial ou moins. Nous utilisons ce fait chaque fois que nous déverrouillons nos iPhones ou envoyons des messages via WhatsApp. Comme il s'avère, Problèmes de NP sont parfaits pour le cryptage; il n'y a qu'une seule façon de résoudre le problème qui déverrouille le cryptage rapidement, vous devez avoir la réponse à l'avance.

CONNEXES: 7 ALGORITHMES ESSENTIELS QUI COURENT LE MONDE

Naturellement, nous aimons le chiffrement, et nous sommes heureux qu'il soit sécurisé pour le moment, mais il y a beaucoup de problèmes dans NP pour lesquels nous avons vraiment, vraiment besoin d'algorithmes efficaces. Malgré les meilleurs efforts de certaines personnes incroyablement intelligentes, cependant, il y a eu très peu de progrès dans la résolution de tous, sauf quelques-uns Problèmes de NP que nous connaissons. Cela a généré l'un des grands problèmes de mathématiques et de calcul non résolus des 50 dernières années: P vs NP, aussi appelé P = NP.

Ce que cette équation demande est que tout Problème NP être résolu en temps polynomial, faisant ainsi Problèmes de NP vraiment Problèmes P qui ont juste besoin d'être correctement résolus, ou sont là Problèmes de NP pour laquelle aucune solution ne peut être trouvée en temps polynomial et donc rester pratiquement insoluble quels que soient les algorithmes que nous développons?

En examinant ces deux ensembles de problèmes, P vs NP, le but est de prouver l'une des deux choses suivantes: soit P = NP, ce qui signifie que dans son ensemble, Problèmes de NP en tant qu'ensemble - y compris ceux que nous connaissons ainsi que ceux que nous pourrions découvrir dans le futur - appartiennent en fait à P et peut être résolu en temps polynomial; ou P NP et quel que soit l’algorithme que nous proposons, il y aura un plancher mathématique sur la complexité temporelle d’un problème et ce plancher est supérieur au temps polynomial.

La réponse à cette question de toute façon est suffisamment importante pour que quiconque trouve la réponse gagne un prix d'un million de dollars de la Clay Mathematics Institute, sans parler de l'installation dans le panthéon de l'informatique en plus de John Von Neumann, Alan Turing, Ada Lovelace et d'autres sommités. .

Pour beaucoup, le problème de P vs NP Il s'agit principalement du fait qu'il existe une lacune dans notre compréhension des mathématiques qui doit être comblée. Les mathématiciens et les scientifiques de toutes les disciplines ont horreur du vide de connaissances, la solution à ce problème est donc importante en principe. Cela dit, la poursuite de P = NP a d'immenses implications dans le monde réel s'il est prouvé que, mathématiquement, P = NP. Pour comprendre pourquoi, nous devons aborder les deux derniers problèmes qui relient tout cela.

NP-Hard et NP-Complete

NP-complet est une catégorie spéciale de Problèmes de NP qui ont des complexités temporelles supérieures au temps polynomial, sont vérifiables en temps polynomial et appartiennent à un ensemble de problèmes connus sous le nom de NP-dur. NP-dur les problèmes sont essentiellement ceux qui sont au moins aussi durs que les plus durs Problème NP, mais il n’est pas nécessaire d’être vérifiable en temps polynomial.

Énumérer tous les sous-ensembles possibles de l'ensemble de chaque atome individuel de l'univers est un NP-dur problème. Nous ne pouvons pas prouver qu'un tel problème est insoluble en temps polynomial, mais il n'y a aucune raison de croire que nous trouverons jamais cet algorithme ou même construirons une machine assez puissante pour l'exécuter et même si quelqu'un nous donnait une réponse, nous ne le ferions pas. même commencer à savoir comment procéder pour le vérifier.

Un autre NP-dur Le problème est d'identifier un coup d'échecs dans un état de plateau donné qui est le meilleur coup absolu que vous puissiez faire. Pour déterminer cela, vous devez savoir que chaque autre mouvement mènera à un pire résultat, et la seule façon dont nous savons comment le déterminer est de suivre chaque chemin de ramification de chaque mouvement, contre-mouvement, etc., c'est possible. avec la position de conseil donnée. Une fois que vous arrivez au résultat final de chaque branche de cet arbre de décision pratiquement infini, vous prendriez alors le meilleur résultat et diriez que c'était le meilleur mouvement que vous auriez pu faire.

Laissant de côté l'impossibilité fonctionnelle de naviguer dans cet arbre au cours des deux prochains milliards de milliards d'années, si vous me dites qu'un mouvement particulier était vraiment le meilleur mouvement possible que vous auriez pu faire, il n'y a aucun moyen pour moi de le vérifier rapidement. Je devrais recourir exactement au même algorithme de permutation par force brute que vous venez d'utiliser pour explorer chaque conséquence de chaque mouvement. La vérification de la solution prendrait exactement le temps nécessaire pour résoudre le problème.

Si cela vous semble familier, c’est parce que c’est le cas. C'est le même problème de base que le Problème de vendeur itinérant, ce qui signifie qu'il s'agit essentiellement d'optimisation. Il s'avère que c'est l'une des caractéristiques déterminantes de NP-complet problèmes; vous n'essayez en réalité que de résoudre un problème qui comporte d'innombrables variantes et ces variantes englobent l'intégralité de ce que nous considérons comme essentiel pour la prise de décision en matière d'affaires, de politique ou de recherche.

L'algorithme pour tout

C'est pourquoi P = NP compte. Nous ne pouvons pas le savoir avec certitude, mais il y a tout lieu de croire que la réponse à cette question passe à travers NP-complet. Tout d'abord, tout algorithme qui renvoie une solution à un NP-complet problème en temps polynomial peut être modifié pour résoudre chaque problème NP-complet problème en temps polynomial, car ils sont tous le même problème à leur noyau.

Pas seulement cela, mais une partie de la définition d'un NP-complet le problème est chaque problème dans NP est réductible à chaque NP-complet problème, ce qui signifie qu'un algorithme qui résout NP-complet en temps polynomial résoudra également tout NP problèmes en temps polynomial également; en d'autres termes, résoudre un NP-complet problème en temps polynomial prouve P = NP par défaut et résout efficacement presque tous les problèmes de calcul les plus difficiles du monde réel littéralement du jour au lendemain.

Donc, cela rend essentiellement l'algorithme qui résout un NP-complet problème en temps polynomial un algorithme pour tout. C'est pourquoi P = NP, cette équation au son étrange et opaque est tellement prometteuse si elle peut être prouvée et la seule vraie façon de le faire est de résoudre un NP-complet problème en temps polynomial. Cet algorithme deviendrait un algorithme qui pourrait débloquer un monde entièrement différent en un instant. Il y a beaucoup d'excitation autour de la possibilité de l'informatique quantique précisément parce que c'est peut-être notre meilleure chance de résoudre NP-complet en temps polynomial, mais il reste à voir si oui ou non.

Le dernier article de notre série sur les algorithmes et le calcul, Algorithmes quantiques et avenir de l'informatique post-classique, peut être trouvé ici


Voir la vidéo: P versus NP: exemple dans un réseau social. Rachid Guerraoui (Juillet 2022).


Commentaires:

  1. Erik

    Je pense que tu as fait l'erreur

  2. Cat

    Je pense que des erreurs sont commises. Essayons de discuter de cela. Écrivez-moi dans PM, cela vous parle.

  3. Taur

    Être direct.

  4. Irwin

    Vous venez de visiter une merveilleuse idée



Écrire un message