Pour mesurer la complexité d’un algorithme, il est dans l’usage de considérer le temps conçu comme un espace discret dont le grain définit l’étape élémentaire. Cette habitude a engendré ce que nous nommons la théorie de la complexité. Cependant comme le fait justement remarquer Gregory Chaitin, le paradoxe de cette mentation c’est qu’elle ignore l’information. Et nous pensons pour notre part que cette idée pour le moins subversive trouve un écho en mathématiques.

Considérons le paradigme de la distribution des nombres premiers. Depuis 1896, nous connaissons le théorème des nombres premiers de la Vallée Poussin démontré via des outils d’analyse complexe. De plus, il existe depuis 1936 une démonstration de ce même résultat par Erdös qui n’utilise que des outils de la théorie des nombres élémentaire. Dans les deux cas, le résultat est le même cependant les méthodes sont radicalement différentes. Laquelle devons-nous considérer comme plus complexe ? Celle de 1896 qui est rapide et élégante ou celle de 1936 qui est longue et astucieuse ? La première doit sa rapidité au fait qu’elle exploite une théorie puissante ainsi chacun de ses pas élémentaires est relativement complexe tandis que la seconde est longue car elle n’exploite que des outils élémentaires afin de ne pas s’élever axiomatiquement parlant. Il est clair que le choix est avant tout doctrinal si nous mettons en balance le temps et l’information. La compacité s’oppose aussi à l’explicitation. La première démonstration est facile car elle s’appuie sur des résultats difficiles, tandis que la seconde est difficile car elle s’appuie sur des résultats faciles.

Ainsi, le point de vue de Chaitin loin de nous paraître comme une exubérance de logicien, nous semble effectif et puissant pour considérer et mesurer la véritable complexité d’une démonstration mathématique surtout si celle-ci doit être codée de manière formelle a posteriori afin d’être comparée à d’autres au sein d’une hiérarchie donnée. Car le temps de l’information semble plus profond que l’information du temps.