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.)

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”.

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

]]>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

]]>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.

]]>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.

]]>(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.