Half-exponential function

In mathematics, a half-exponential function is a function ƒ that, if composed with itself, results in an exponential function:^[1]^[2]

f(f(x))=ab^{x}.\,

Another definition is that ƒ is half-exponential if it is non-decreasing and ƒ⁻¹(x^C) ≤ o(log x). for every C > 0.^[3]

It has been proven that if a function ƒ is defined using the standard arithmetic operations, exponentials, logarithms, and real-valued constants, then ƒ(ƒ(x)) is either subexponential or superexponential.^[4]^[5] Thus, a Hardy L-function cannot be half-exponential.

There are infinitely many functions whose self-composition is the same exponential function as each other. In particular, for every $A$ in the open interval $(0,1)$ and for every continuous strictly increasing function g from $[0,A]$ onto $[A,1]$ , there is an extension of this function to a continuous monotonic function $f$ on the real numbers such that $f(f(x))=\exp x$ .^[6] The function $f$ is the unique solution to the functional equation

f(x)={\begin{cases}g(x)&{\mbox{if }}x\in [0,A],\\\exp(g^{{-1}}(x))&{\mbox{if }}x\in (A,1],\\\exp(f(\ln(x)))&{\mbox{if }}x\in (1,\infty ),\\\ln(f(\exp(x)))&{\mbox{if }}x\in (-\infty ,0).\\\end{cases}}

Half-exponential functions are used in computational complexity theory for growth rates "intermediate" between polynomial and exponential.^[2]

References

↑ Kneser, H. (1950). "Reelle analytische Lösungen der Gleichung φ(φ(x)) = e^x und verwandter Funktionalgleichungen". Journal fur die reine und angewandte Mathematik. 187: 56–67.
1 2 Peter Bro Miltersen; N. V. Vinodchandran; Osamu Watanabe (1999). "Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy". Lecture Notes in Computer Science. 1627: 210–220. doi:10.1007/3-540-48686-0_21.
↑ Alexander A. Razborov; Steven Rudich (August 1997). "Natural Proofs". Journal of Computer and System Sciences. 55 (1): 24–35. doi:10.1006/jcss.1997.1494.
↑ http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth
↑ "Shtetl-Optimized » Blog Archive » My Favorite Growth Rates". Scottaaronson.com. 2007-08-12. Retrieved 2014-05-20.
↑ 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 943525.

External links

This article is issued from Wikipedia - version of the 6/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Half-exponential function

See also

References

External links