In mathematics, a half-exponential function is a functional square root of an exponential function. That is, a function such that composed with itself results in an exponential function:[1][2]
for some constants and .
Impossibility of a closed-form formula
If a function is defined using the standard arithmetic operations, exponentials, logarithms, and real-valued constants, then is either subexponential or superexponential.[3] Thus, a Hardy L-function cannot be half-exponential.
Construction
Any exponential function can be written as the self-composition for infinitely many possible choices of . In particular, for every in the open interval and for every continuous strictly increasing function from onto , there is an extension of this function to a continuous strictly increasing function on the real numbers such that .[4] The function is the unique solution to the functional equation
A simple example, which leads to having a continuous first derivative everywhere, is to take and , giving
Application
Half-exponential functions are used in computational complexity theory for growth rates "intermediate" between polynomial and exponential.[2] A function grows at least as quickly as some half-exponential function (its composition with itself grows exponentially) if it is non-decreasing and , for every .[5]
See also
- Iterated function – Result of repeatedly applying a mathematical function
- Schröder's equation – Equation for fixed point of functional composition
- Abel equation – Equation for function that computes iterated values
References
- ↑ Kneser, H. (1950). "Reelle analytische Lösungen der Gleichung φ(φ(x) = ex und verwandter Funktionalgleichungen". Journal für die reine und angewandte Mathematik. 187: 56–67. MR 0035385.
- 1 2 Miltersen, Peter Bro; Vinodchandran, N. V.; Watanabe, Osamu (1999). "Super-polynomial versus half-exponential circuit size in the exponential hierarchy". In Asano, Takao; Imai, Hiroshi; Lee, D. T.; Nakano, Shin-ichi; Tokuyama, Takeshi (eds.). Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26–28, 1999, Proceedings. Lecture Notes in Computer Science. Vol. 1627. Springer. pp. 210–220. doi:10.1007/3-540-48686-0_21. MR 1730337.
- ↑ van der Hoeven, J. (2006). Transseries and real differential algebra. Lecture Notes in Mathematics. Vol. 1888. Springer-Verlag, Berlin. doi:10.1007/3-540-35590-1. ISBN 978-3-540-35590-8. MR 2262194. See exercise 4.10, p. 91, according to which every such function has a comparable growth rate to an exponential or logarithmic function iterated an integer number of times, rather than the half-integer that would be required for a half-exponential function.
- ↑ Crone, Lawrence J.; Neuendorffer, Arthur C. (1988). "Functional powers near a fixed point". Journal of Mathematical Analysis and Applications. 132 (2): 520–529. doi:10.1016/0022-247X(88)90080-7. MR 0943525.
- ↑ Razborov, Alexander A.; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences. 55 (1): 24–35. doi:10.1006/jcss.1997.1494. MR 1473047.