Algorithmes & émergenceComplexité algorithmique

Facile à vérifier, dur à résoudre

Vérifier un sudoku prend quelques secondes ; le résoudre peut prendre une éternité

Repérer une erreur dans un sudoku fini prend quelques secondes. Alors pourquoi remplir la même grille peut-il te prendre une heure ?

Tu vas découvrir

  • Le peu d'étapes qu'exige la vérification
  • Pourquoi résoudre oblige à tant deviner
  • Le puzzle à 2 millions de dollars jamais fini

Pourquoi c'est important

Emplois du temps, livraisons et casse-tête partagent tous cet écart, qui mène à l'une des plus grandes questions ouvertes des maths.

Environ 3 min6 diapositives interactives · 5 questionsLeçon 656 · 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. 657Complexité algorithmiqueP versus NPUne question à un million de dollars : trouver est-il plus dur que vérifier ?