Fonction exponentielle double

Une fonction exponentielle double est une fonction exponentielle dont l’exposant est lui-même une fonction exponentielle. La forme générale est : Cette fonction croît plus vite qu’une exponentielle simple. Par exemple, pour a = b = 10 : f(−1) ≈ ; f(0) = 10 ; f(1) = 1010 ; f(2) = 10100 = googol ; f(3) = 101000 ; f(100) = 1010100 = googolplex. Les factorielles croissent plus vite que les exponentielles, mais beaucoup plus lentement que les exponentielles doubles. La fonction hyper-exponentielle et la fonction d'Ackermann croissent encore plus vite. L’inverse d’une fonction exponentielle double est un logarithme double. Aho et Sloane remarquèrent que, pour certaines suites entières importantes, chaque terme successif est égal au carré du terme précédent plus une constante. Ils montrèrent que de telles suites peuvent être calculées en arrondissant à l’entier le plus proche les valeurs d’une exponentielle double de la forme : Les suites d'entiers qui suivent ce schéma sont, en particulier : Les nombres de Fermat : Les nombres doubles de Mersenne : Les termes successifs de la série de Sylvester () : où E ≈ est la constante de Vardi (). L’arité des opérateurs logiques : Plus généralement, si la nième valeur d'une suite d’entiers est proportionnelle à une fonction exponentielle double de n, Ionescu et Stanica qualifient la série de « presque exponentielle double » et indiquent les conditions selon lesquelles elle peut être calculée comme l’arrondi inférieur (arrondi par troncation) d’une série exponentielle double, plus, éventuellement, un coefficient constant. D’autres suites de ce type sont : Les nombres premiers 2, 11, , ... () où A ≈ est la constante de Mills. Dans la théorie de la complexité algorithmique, certains algorithmes sont de complexité exponentielle double : Procédures de décision dans l’arithmétique de Presburger ; Calcul d'une base de Gröbner (dans le cas le plus défavorable) ; Trouver en théorie de la décision un ensemble complet unifié d’opérateurs associatifs-commutatifs Résolution des problèmes en CTL+ (qui sont, en fait en 2-EXP-complets) ; L’élimination des quantificateurs sur un corps réel clos nécessite un temps croissant au moins selon une exponentielle double (mais on ne sait même pas si elle est calculable en un temps de classe ELEMENTARY).