Half-exponential function

In mathematics, a half-exponential function is a function ƒ so that if ƒ is composed with itself the result is exponential:[1]

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

Another definition is that ƒ is half-exponential if it is non-decreasing and ƒ−1(xC)  o(log x). for every C > 0.[2]

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.[3] [4] 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.[5] 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.[1]

See also

References

  1. 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.
  2. Alexander A. Razborov and Steven Rudich (August 1997). "Natural Proofs". Journal of Computer and System Sciences 55 (1): 24–35. doi:10.1006/jcss.1997.1494.
  3. http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth
  4. "Shtetl-Optimized » Blog Archive » My Favorite Growth Rates". Scottaaronson.com. 2007-08-12. Retrieved 2014-05-20.
  5. 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

  1. http://mathoverflow.net/questions/12081/does-the-exponential-function-have-a-square-root
  2. http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth
This article is issued from Wikipedia - version of the Monday, April 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.