Comments on: My Favorite Growth Rates

By: Gil

Gil — Sun, 26 Aug 2007 13:47:49 +0000

Neil,

From the point of view of complexity theoretic polynomial reductions, exp (n^c) where c>0 is still exponential. (This is the reason for the slightly different terminology.) So I would not expect to find NP-complete problems that are sub-exponential in the sense of CS: (namely exp (o(n)). Or in other words, the belief is that NP-hard problems are indeed exponential (in the CS sense).

(Regarding quasi-polynomial growth; One very lovely problem is to distinguish between Boolean functions that can be computed by a bounded depth polynomial size Boolean circuits to those which requires quasi-polynomial size bounded depth circuits; e.g. we can find a clique of size log n in a graph with n verices via a depth-2 size n^log n
Boolean circuit. Show that this cannot be done in a polynomial size depth-1000000 circuit.)

By: Neil Dickson

Neil Dickson — Sat, 25 Aug 2007 22:29:05 +0000

Thanks for the clarification. That’s some interesting terminology; it just sounds a bit odd in that then there are NP-hard problems that do not take exponential time simply because “exponential” is defined differently. Using your terminology, several NP-hard problems that I know would have a “sub-exponential” worst case and some would have a “quasi-polynomial” average case.

Also, “quasi-polynomial” means something different in terms of abstract algebra: http://en.wikipedia.org/wiki/Quasi-polynomial
Perhaps “super-polynomial” would be a possible name for it to have consistent naming with your definition of “sub-exponential”. However, then it makes the ambiguity more evident in that “sub-exponential” usually refers to “anything less than exponential” just as “super-polynomial” usually refers to “anything greater than polynomial”.

By: Peter Shor

Peter Shor — Sat, 25 Aug 2007 21:24:31 +0000

You left out inverse Ackermann star, the number of times you need to iterate the inverse Ackermann function starting with n before you reduce the number to a constant. And 2^inverse Ackermann(n) is the correct growth rate for Davenport-Schinzel sequences of order 4, as I showed with Pankaj Agarwal and Micha Sharir.

By: Gil

Gil — Sat, 25 Aug 2007 19:23:25 +0000

On the exponential side let 1>c>0

exp (n) is exponential (and also exp (an) a>0)

exp (n^c) is sub-exponential (CS people will call it mildly exponential)

exp exp (log n^c) is sub-sub exponential (CS: sub-exponential)

exp exp exp (log log n)^c is sub-sub-sub exponential (CS: sun-sub-exponential)

and so on. (The difference between the math and CS usage is similar to the difference use of Billion and Trillion between the US and Europe)

so the nice thing for f: f(f(n))=exp (n) is that it is bigger than all the quasi-quasi-quasi-quasi …-polynomial growth and smallet than all the sub-sub-sub-sub-…-exponential

By: Gil

Gil — Sat, 25 Aug 2007 19:18:06 +0000

Dear Neil,
The terminology I find useful is the following: Let c>1

n^c is polynomial

exp ((log n)^c) is quasi-polynomial (e.g. n^log n)

exp (exp (loglog n)^c)) is quasi-quasi-polynomial

exp (exp (exp (log log log n)^c))) is quasi-quasi-quasi polynomial and so on…

On the exponential side let 0

By: Neil Dickson

Neil Dickson — Sat, 25 Aug 2007 18:30:46 +0000

That’s quite a limited definition of “exponential”, since by that definition, e^(sqrt(n)) is not exponential, when most would consider it to be exponential. By “exponential”, I meant 2^(small_omega(log n)), or alternatively, n^(small_omega(1)).

By: DavidS

DavidS — Sat, 25 Aug 2007 17:56:39 +0000

n^{log n} is not exponential, if by exponential you mean “grows faster than e^{c n} for some positive c”. As you point out, it is e^{(log n)^2}, which is much less than e^{cn}. Indeed, n^{log n} is the standard example of a function which grows faster than n^k for any k but slower than e^{c n} for any positive c.

By: Neil Dickson

Neil Dickson — Sat, 25 Aug 2007 17:08:22 +0000

The question as to whether f:f(f(n))=2^n is exponential or not is actually much simpler than finding a closed form of it or approximation to it.

n^(logn) is exponential. It is equal to 2^((logn)^2). Let this be g(n).

g(g(n)) = 2^((log(2^((logn)^2)))^2)
= 2^(((logn)^2)^2)
= 2^((logn)^4)

g(g(n)) is then o(2^n) and g(n) is exponential. Therefore f(n) must also be exponential.

By: DavidS

DavidS — Fri, 24 Aug 2007 17:44:52 +0000

I’m sorry! I forget about greater and less than signs!

after the expression for phi, my previous comment should read “with lambda less than 1, then there is an analytic function u defined in a neighborhood of 0 with phi(u(x))=u(lambda x). It seems to me that the same argument should hold when lambda is great than 1 by looking at the inverse function to phi, but that’s my thought, not his. He doesn’t give a proof of the assertion, however.

By: DavidS

DavidS — Fri, 24 Aug 2007 17:42:19 +0000

I'll be out of touch with the internet next week, so I want to let anyone still reading know that I haven't forgotten this thread. In particular, I am curious why the sequences Gil presents appear to have a roughly linear growth. In the mean time, two very quick citations to back up some of what I've said. (1) I still haven't gotten around to looking up the original, but Concrete Mathematics, in chapter 9, cites the same result of G.H. Hardy that I did and confirms that the reference is Orders of Infinity. (2) In Asymptotic Methods in Analysis , by N. G. de Bruijn, (Section 8.2, if I recall correctly, I looked this up in my office yesterday but am now not there) de Brujin states that, if phi(x) is an analytic function of the form phi(x)=lambda x + ... with lambda 1 by looking at the inverse function to phi, but that's my thought, not his. He doesn't give a proof of the assertion, however.