En mathématiques, une fonction demi-exponentielle ou semi-exponentielle est une racine carrée fonctionnelle d'une fonction exponentielle. Autrement dit, une fonction telle que composée avec elle-même donne une fonction exponentielle:
pour certaines constantes
Impossibilité d'une forme fermée Si une fonction est définie à l'aide des opérations arithmétiques standard, de l'exponentiation, des logarithmes et des constantes réelles, alors est soit sous-exponentielle, soit super-exponentielle Voir 4.10, p. 91, selon lequel toute telle fonction a un taux de croissance comparable à une fonction exponentielle ou logarithmique itérée un nombre entier de fois, plutôt que le demi-entier qui serait requis pour une fonction demi-exponentielle.. Ainsi, une fonction de Hardy ne peut pas être semi-exponentielle.
Construction Toute fonction exponentielle peut être écrite comme l'auto-composition pour une infinité de choix possibles de . En particulier, pour chaque dans l'intervalle ouvert et pour toute fonction continue strictement croissante depuis sur , il existe un prolongement de cette fonction vers une fonction continue strictement croissante sur les nombres réels tels que . La fonction est l'unique solution de l'équation fonctionnelle droite|vignette|300x300px| Exemple de fonction semi-exponentielle Un exemple simple, qui conduit à avec une dérivée continue partout, consiste à prendre et , donnant
Application Les fonctions demi-exponentielles sont utilisées dans la théorie de la complexité informatique pour les taux de croissance « intermédiaires » entre polynôme et exponentiel. Une fonction croît au moins aussi vite qu'une fonction demi-exponentielle (sa composition avec elle-même croît de façon exponentielle) si elle est non décroissante et , pour
Voir aussi
Fonction itérée Équation de Schröder
Références
Liens externes
Does the exponential function have a (compositional) square root? "Closed-form" functions with half-exponential growth
Catégorie:Algorithme Catégorie:Théorie de la complexité des algorithmes