Les fanas de Tetris vont être flattés. Des mathématiciens du Massachusetts Institute of Technology (MIT) se sont penchés sur leur passe-temps favori pour conclure que c'était un jeu... difficile. Il semblerait même qu'il appartienne à la crème des problèmes mathématiques : la famille des problèmes «NP-complets».

Tetris, pour les néophytes du clavier, est un jeu vidéo ultracélèbre né en 1985 dans une université russe et qui a rapidement conquis les consoles et les ordinateurs du monde entier. Son but est d'empiler des formes géométriques pour constituer un maximum de lignes, lesquelles disparaissent au fur et à mesure qu'elles sont complétées. Qu'on soit le meilleur joueur du monde ou non, on perd forcément à un moment donné. Et on ne peut pas créer un programme qui pourrait mettre Tetris à terre, car le jeu est un problème «NP-complet», comme le Démineur.

Branches. «Ce sont des problèmes difficiles à résoudre rapidement», explique Susan Hohenberger, du labo de théorie du calcul du MIT. «Il faut des années à un ordinateur pour calculer l'ensemble des solutions...» Voire des millénaires, selon la complexité du problème... La recherche d'une solution à un problème «NP-complet» consiste à parcourir un arbre. Dans cet arbre, on trouve l'ensemble des solutions possibles, chaque branche représentant une éventuelle solution. Evidemment, l'espace des solutions croît exponentiellement selon la taille de l'arbre. L'unique façon d'obtenir une solution correcte est d'étudier l'ensemble des