Half-exponential function

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

Another definition is that ƒ is half-exponential if it is non-decreasing and ƒ−1(xC)  o(logx). 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 in the open interval and for every continuous strictly increasing function g from onto , there is an extension of this function to a continuous strictly increasing function on the real numbers such that .[6] The function is the unique solution to the functional equation

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

References

  1. 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.
  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. pp. 210–220. CiteSeerX 10.1.1.16.2908. doi:10.1007/3-540-48686-0_21. ISBN 978-3-540-66200-6.
  3. 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.
  4. "Fractional iteration - "Closed-form" functions with half-exponential growth".
  5. "Shtetl-Optimized » Blog Archive » My Favorite Growth Rates". Scottaaronson.com. 2007-08-12. Retrieved 2014-05-20.
  6. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.