Blog personnel d'Arthur Milchior

Je vais aller faire un stage dans un laboratoire de "(computational) complexity", ou en français complexité (calculatoire). En premier lieu, j'ai envie d'essayer d'expliquer de manière simple pourquoi je trouve ce sujet passionnant. L'explication sera peut-être un peu mystique, car je suis de ceux qui pensent qu'on découvre les mathématiques, mais qu'on ne les invente pas. Cela n'a pas forcément beaucoup d'importance.

Je vais vous donner un exemple à partir d'un problème classique en informatique, transposé dans la vie de tous les jours.

Vous invitez un tas d'amis à diner et pour l'occasion avez mis le couvert sur une grande table ronde. Vous avez plusieurs cercles d'amis qui ne se connaissent pas nécessairement tous entre eux, d'ailleurs vous avez envie de permettre à des gens de se découvrir et pour cela vous allez assignez des places à vos invités, avec un petit carton avec leur noms sur leurs assiettes de manière à ce que que toute personne soit assise entre deux personnes qu'elle ne connait pas. Eh bien, en supposant que vous savez exactement qui connait qui, le simple fait de savoir s'il est possible de placer tout le monde autour de la table de manière à respecter cette contrainte est, en général, extrêmement dur !

On appelle "Algorithme" une méthode qui permet de systématiquement résoudre un problème. Un algorithme peut être d'essayer toutes les manières possible de placer les gens autour de la table, et voir si il y en a une qui est correcte. Faire comme cela va prendre un temps exponentiel, c'est à dire que pour chaque invité supplémentaire, le temps de calcul va doubler ! Malheureusement, il n'existe pas (encore ?) d'algorithme fondamentalement meilleur, au point qu'on dit que celui qui saurait résoudre ce problème aurait à la fois le prix Turing et la médaille Fields, qui sont les équivalents des prix Nobel d'informatique et de mathématique respectivement.

On ne sait pas faire ça, mais on peut se poser tout un tas de question, en premier lieu, chercher dans quels cas particulier on sait faire le calcul facilement. Par exemple, si une personne connait tous le monde, il est évident que c'est raté. Si personne ne connait personne c'est évident: on place tout le monde n'importe comment ! Mais entre les deux, qu'est-ce qu'on peut dire ? Par exemple, si chaque personne ne connait pas plus que la moitié des personnes, on sait qu'il est toujours possible de placer les gens autour de la table, et on sait même trouver assez rapidement comment placer les gens, quand le nombre d'invité double, le temps qu'on met à chercher la solution est multiplié seulement par 25^[1], ce qui est un net progrès par rapport au cas général. Mais on peut aussi réfléchir à d'autres moyens de calculer, je ne connais pas les réponses dans le cas général, et je ne crois pas qu'elles soient toutes connues:

-Et si je laissais les invités se débrouiller entre eux^[2], est-ce qu'ils réussiraient rapidement, est-ce qu'il faudrait que tous parlent à tout le monde, ou est-ce qu'ils peuvent se débrouiller juste en parlant avec ceux avec qui ils sont amis/ne sont pas amis ^[3]?

-Et si je jetais les cartons aux hasard en espérant avoir un bon résultat ^[4], combien de fois je dois réessayer avant de me dire que ça doit être impossible ? Combien d'essai je dois faire avant d'avoir une chance sur deux d'avoir bon ?

-Si je demandais à un génie^[5] de me donner la solution, est-ce que je pourrais vérifier rapidement qu'il ne s'est pas moqué de moi. Eh bien oui, il suffit qu'il nous dise comment mettre les cartons sur les assiettes et de vérifier qu'effectivement personne ne connait son voisin.

Enfin, on peut choisir de changer légèrement de problème:

-Et si je permettais à un petit nombre de personne de s'asseoir à coté d'un ami à lui ? Voir carrément de deux amis à lui ? A partir de quel nombre de personne le problème devient simple à résoudre ? 10 personnes ? la moitié des personnes ?

-Et si finalement je décide de faire que tout le monde connaisse ses deux voisins, est-ce que ça va être plus simple ? Eh bien non. C'est en fait exactement le même problème^[6]

-Imaginez des villes sur une cartes, certaines relié par des routes: vous voulez allez dans toutes les villes une fois et une seule en empruntant les routes de votre carte, est-ce que c'est possible ? Vous allez me dire, qu'est-ce que ça a à voir ? Eh bien c'est exactement le même problème en imaginant que les villes sont des personnes et que les routes existent si et seulement si les deux villes au bout de la route ne se connaissent pas^[7]. Plus généralement le but du jeu est de voir quand un problème est identique à un autre problème, ce qui nous dit que si on sait résoudre l'un rapidement, on sait aussi résoudre l'autre.

Enfin, et c'est peut être la question la plus fondamentale de la complexité, pourquoi diantre est-ce qu'on n'arrive pas à faire ce calcul rapidement ? Est-ce vraiment intrinsèquement difficile, la nature même du problème nous oblige-t-elle a y passer du temps, et n'y a t-il aucun moyen d'y arriver ou est-ce que simplement jusqu'à aujourd'hui les humains ont été trop bête ? On sait, mathématiquement, que certains problèmes ne peuvent pas être résolu rapidement, mais pour celui là on ne sait pas grand chose.

Là où ça nous embête, c'est que si on ne sait pas grand chose, on sait quand même que des centaines d'autres problèmes sont aussi difficile que celui là, c'est à dire que si vous savez résoudre un de ces problèmes, vous savez résoudre tous les autres et, inversement, si vous savez qu'il est impossible d'en résoudre un rapidement, vous savez automatiquement que les autres ne peuvent pas non plus être résolus rapidement.

Pour dire ça autrement, on ne sait pas si, quand on sait résoudre rapidement un problème avec un génie auquel on ne fait pas confiance^[8], on sait toujours le résoudre efficacement sans génie ? On suppose que le génie est indispensable, mais on ne sait pas non plus le prouver, et c'est ce qui est à la fois très frustrant et fait tout l'intérêt, si je peu dire, de la complexité: le graal, c'est de se débarrasser d'un génie.