Conjecture de Hartmanis-Stearns

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.

Formulation

Un mot infini $x$ 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 $x$ 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é $n$ , écrit les lettres successives de ce mot en unaire sur sa bande de sortie, en temps $O(n)$ ^[2]^,^[3].

La conjecture de Hartmanis-Stearns stipule que si $x$ est un nombre réel dont le développement dans une certaine base $b\geq 2$ (par exemple, le développement décimal de $b=10$ ) est calculable en temps réel, alors $x$ 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 $O(n\log(n)$ ^[3].

Résultats partiels

Un résultat partiel a été démontré par Boris Adamczewski et Yann Bugeaud^[5] (une autre démonstration antérieure, par John H. Loxton et Alfred van der Poorten^[6], s'est avérée incomplète) : un nombre $x$ est rationnel ou transcendant si son développement dans une base $b\geq 2$ donnée est une suite automatique. Ce résultat a ensuite été généralisé par Boris Adamczewski, Julien Cassaigne et Marion Le Gonidec^[4] aux suites engendrées par des automates à pile déterministes.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hartmanis–Stearns conjecture » (voir la liste des auteurs).

↑ Juris Hartmanis et Richard E. Stearns, « On the computational complexity of algorithms », Transactions of the American Mathematical Society, vol. 117,‎ 1965, p. 285–306 (DOI 10.2307/1994208, JSTOR 1994208, MR 0170805)
↑ Patrick C. Fischer, Albert R. Mayer et Arnold L. Rosenberg, « Time-restricted sequence generation », Journal of Computer and System Sciences, vol. 4, n^o 1,‎ 1970, p. 50–73 (DOI 10.1016/S0022-0000(70)80012-5)
Richard Lipton, « Why The Hartmanis-Stearns Conjecture Is Still Open »
Boris Adamczewski, Julien Cassaigne et Marion Le Gonidec, « On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited », Transactions of the American Mathematical Society, vol. 373,‎ 2020, p. 3085–3115 (arXiv 1601.02771)
↑ Boris Adamczewski et Yann Bugeaud, « On the complexity of algebraic numbers I. Expansions in integer bases », Annals of Mathematics, vol. 165, n^o 2,‎ 2007, p. 547–565 (DOI 10.4007/annals.2007.165.547, arXiv math/0511674)
↑ John H. Loxton et Alfred van der Poorten, « Arithmetic properties of automata: regular sequences », Journal für die reine und angewandte Mathematik, vol. 392,‎ 1988, p. 57–69 (lire en ligne)

Voir aussi

Problèmes non résolus en informatique

Portail de l'informatique théorique
Arithmétique et théorie des nombres

[original-1] Juris Hartmanis et Richard E. Stearns, « On the computational complexity of algorithms », Transactions of the American Mathematical Society, vol. 117,‎ 1965, p. 285–306 (DOI 10.2307/1994208, JSTOR 1994208, MR 0170805)

[fmr-2] Patrick C. Fischer, Albert R. Mayer et Arnold L. Rosenberg, « Time-restricted sequence generation », Journal of Computer and System Sciences, vol. 4, n^o 1,‎ 1970, p. 50–73 (DOI 10.1016/S0022-0000(70)80012-5)

[lipton-blog-3] Richard Lipton, « Why The Hartmanis-Stearns Conjecture Is Still Open »

[acg-4] Boris Adamczewski, Julien Cassaigne et Marion Le Gonidec, « On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited », Transactions of the American Mathematical Society, vol. 373,‎ 2020, p. 3085–3115 (arXiv 1601.02771)

[adamczewski-bugeaud-5] Boris Adamczewski et Yann Bugeaud, « On the complexity of algebraic numbers I. Expansions in integer bases », Annals of Mathematics, vol. 165, n^o 2,‎ 2007, p. 547–565 (DOI 10.4007/annals.2007.165.547, arXiv math/0511674)

[loxton-poorten-6] John H. Loxton et Alfred van der Poorten, « Arithmetic properties of automata: regular sequences », Journal für die reine und angewandte Mathematik, vol. 392,‎ 1988, p. 57–69 (lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]