# Faster than polynomials, Slower than exponentials

August 23, 2008 2:47 PM Subscribe

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.

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.

*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

posted by pmdboi at 3:11 PM on August 23, 2008 [1 favorite]

**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 [1 favorite]

Thanks everyone!

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

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

posted by leapfrog at 5:28 AM on August 25, 2008

« Older Why aren't my images showing up on my (drupal... | How do I backup/copy just the new stuff? Newer »

This thread is closed to new comments.

posted by saeculorum at 2:59 PM on August 23, 2008