Structures de données et algorithmes cs.DS

Extraire une seule puce défectueuse parmi un million, sans aucun indice sur la nature du défaut, est un problème classique de chercher une aiguille dans une botte de foin. Un ordinateur classique testerait chaque puce une par une.

La salle de bal se remplit d'invités. Chaque arrivée est une requête, et la tâche du maître de danse est de trouver le partenaire idéal. On peut unir deux personnes dès qu'elles sont proches, et la paire sera parfaite, mais que se passe-t-il si le partenaire idéal arrive une minute plus tard ? Si l'on tarde, la lassitude des personnes en attente s'accumule : certains s'ennuient, d'autres perdent patience.

Automne 1956. Kurt Gödel écrit sur une feuille de papier une question adressée à John von Neumann, mourant : peut-on vérifier la satisfiabilité d'une formule booléenne plus rapidement qu'en les essayant toutes ? La réponse viendra 69 ans plus tard — et se révélera être la morsure d'un ouroboros logique, le serpent mythique qui se dévore la queue. Le serpent naît du hasard.