Half exponential function

In mathematics, a half-exponential function is a function ƒ that, if composed with itself, results in an exponential function:

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

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. 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 . The function f 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.