Conjecture de Hartmanis-Stearns
From Wikipedia, the free encyclopedia
En informatique théorique et en mathématiques, la conjecture de Hartmanis-Stearns est un problème non résolu, nommé d'après Juris Hartmanis et Richard E. Stearns, qui l'ont formulé en 1965 dans un article intitulé « On the computational complexity of algorithms », article qui est à la base du domaine de la théorie de la complexité computationnelle[1], et qui leur a valu à ce titre le prix Turing en 1993.
Un mot infini est dit calculable en temps réel s'il existe une machine de Turing à plusieurs bandes qui, fonctionnant sans entrée, écrit les lettres successives du mot sur sa bande de sortie, en un temps borné entre l'émission deux lettres successives. De manière équivalente, s'il existe une machine de Turing à plusieurs bandes qui, pour un entier naturel donné , écrit les lettres successives de ce mot en unaire sur sa bande de sortie, en temps [2],[3].
La conjecture de Hartmanis-Stearns stipule que si est un nombre réel dont le développement dans une certaine base (par exemple, le développement décimal de ) est calculable en temps réel, alors est rationnel ou transcendant[3],[4].
Conséquence
La conjecture a pour conséquence notable qu'il n'existe pas d'algorithme de multiplication d'entiers en temps linéaire, alors qu'on connaît un algorithme en [3].
