Content deleted Content added
Ah, it's a lower bound not an upper bound |
move to where it belongs |
||
Line 10:
: <math>f(f(x)) = ab^x.</math>
If a function ''ƒ'' is defined using the standard arithmetic operations, exponentials, [[logarithm]]s, and [[Real number|real]]-valued constants, then ''ƒ''(''ƒ''(''x'')) is either subexponential or superexponential.<ref>{{Cite web | url=https://mathoverflow.net/q/45477 | title=Fractional iteration - "Closed-form" functions with half-exponential growth}}</ref><ref>{{cite web|url=http://www.scottaaronson.com/blog/?p=263#comment-7283 |title=Shtetl-Optimized » Blog Archive » My Favorite Growth Rates |publisher=Scottaaronson.com |date=2007-08-12 |accessdate=2014-05-20}}</ref> Thus, a [[Hardy field#Examples|Hardy ''L''-function]] cannot be half-exponential.
Line 53 ⟶ 51:
</math>
Half-exponential functions are used in [[computational complexity theory]] for growth rates "intermediate" between polynomial and exponential.<ref name="miltersen"/> A function ''ƒ'' grows at least as quickly as some half-exponential function (its composition with itself grows exponentially) if it is [[Monotonic function|non-decreasing]] and ''ƒ''<sup>−1</sup>(''x''<sup>''C''</sup>) ≤ o(log ''x''), for every ''C'' > 0.<ref>{{cite journal |author1=Alexander A. Razborov |author2=Steven Rudich |title=Natural Proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |date=August 1997 |pages=24–35 |doi=10.1006/jcss.1997.1494|doi-access=free }}</ref>
{{see also|Iterated function| Schröder's equation|
| |||