In mathematics, a half-exponential function is a function ƒ so that if ƒ is composed with itself the result is exponential:
Another definition is that ƒ is half-exponential if it is non-decreasing and ƒ−1(xC) ≤ o(log x). for every C > 0.
It has been proven that every function ƒ composed of basic arithmetic operations, exponentials, and logarithms, then ƒ(ƒ(x)) is either subexponential or superexponential: half-exponential functions are not expressible in terms of elementary functions.
||The factual accuracy of part of this article is disputed. The dispute is about inaccurate formulation?. (May 2014)|
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 monotonic function on the real numbers such that . In particular,
- Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe. "Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy". Lecture Notes in Computer Science Volume 1627, 1999, pp 210–220.
- Alexander A. Razborov and Steven Rudich, "Natural Proofs", ournal of Computer and System Sciences, Volume 55, Issue 1, August 1997, pages 24–35
- "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.