Algorithmes & émergenceComplexité algorithmique

P versus NP

Une question à un million de dollars : trouver est-il plus dur que vérifier ?

Un million de dollars attend qui répondra à une question sur les casse-tête. Pourquoi personne ne l'a réclamé depuis 2000 ?

Tu vas découvrir

  • Ce que « rapide » veut dire pour un ordinateur
  • Pourquoi une réponse briserait le chiffrement
  • Sur quoi parient la plupart des experts

Pourquoi c'est important

Le chiffrement de ta banque, les tournées de livraison et même les maths dépendent de ceci : trouver est-il vraiment plus dur que vérifier ?

Environ 4 min7 diapositives interactives · 5 questionsLeçon 657 · Zone 73

Jouer cette leçon

Gratuit dans ton navigateur ou sur iPhone

Plus dans cette zone

  1. 649NombresLes logarithmesPourquoi les séismes et le son utilisent des échelles étranges
  2. 650Génie biomédicalLa main contrôlée par la penséeLes signaux des muscles peuvent faire bouger une main artificielle
  3. 651TopologieLa bouteille de KleinUne bouteille sans intérieur qui ne peut pas exister dans notre monde
  4. 652Fondements des probabilitésLe paradoxe de BertrandUne question sur une ligne au hasard a trois bonnes réponses
  5. 653Histoire du logicielLinux, « juste un passe‑temps »Le projet perso d'un étudiant fait aujourd'hui tourner la plupart des serveurs du monde
  6. 654Provenance des contenusLe filigrane de l'IALes contenus générés peuvent porter des indices cachés sur leur origine
  7. 655Exploration spatialeLe point bleu pâleVue à 6 milliards de kilomètres, la Terre est un grain dans un rayon de soleil
  8. 656Complexité algorithmiqueFacile à vérifier, dur à résoudreVérifier un sudoku prend quelques secondes ; le résoudre peut prendre une éternité