Faster than polynomials, Slower than exponentials

August 23, 2008 2:47 PM

Is there anything "in between" polynomials and exponentials?

Does there exist a real-valued function f: R -> R such that
i) the limit (as x goes to infinity) of f(x) / a^x = 0 for all a > 1, and
ii) the limit (as x goes to infinity) of x^n / f(x) = 0 for all positive integers n.

In down to earth terms, "f(x) grows slower than any exponential, and faster than any polynomial."

This came up in a discussion about algorithms. "There are polynomial time algorithms, and exponential time algorithms. Well, is there anything in between?"

Maybe this is too technical a question for AskMe, but I'm sure the answer is known to some computer programmers, and I respect your guys knowledge on computer stuff.

Things I've tried so far:
Rephrasing the question as a statement about exponentially decaying functions, or about functions blowing up at the origin.
Taking the log of both sides.
Considering trig functions like sec(x), which has a pole at pi/2, combined with the homeomorphism between (-pi/2, pi/2) and the real line via the function arctan(x). This didn't seem to work, but I'm not entirely sure.
Randomly flipping through functional analysis textbooks for statements about the topology of the space of integrable functions. I think the function in question would have to be n-Schwartz for every n, or something like that.

posted by metastability to science & nature (5 comments total)

If you are approaching this from an algorithmic complexity perspective, then the answer you're looking for is algorithms that have super-polynomial runtime. The "textbook example" of such an algorithm is the quadratic sieve. It is the only practical algorithm I know of that has that property, but I imagine you could find much more from Google and/or a bit of research.
posted by saeculorum at 2:59 PM on August 23, 2008

There are polynomial time algorithms, and exponential time algorithms. Well, is there anything in between?

This is a slightly different question. Problems that can be solved in polynomial space and unlimited time include all the polynomial problems, and are included in the problems that can be solved in exponential time. As Wikipedia puts it:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Of course if you want to think strictly in terms of time complexity, there are sub-exponential time algorithms, as saeculorum points out.
posted by grouse at 3:06 PM on August 23, 2008

Going off of saeculorum's link, it seems like f(x) = e^√x satisfies (i) and (ii).
posted by pmdboi at 3:11 PM on August 23, 2008

Thanks everyone!
posted by metastability at 3:26 PM on August 23, 2008

Sounds like a Superpolylogarithmic subexponential function to me.
posted by leapfrog at 5:28 AM on August 25, 2008