6
$\begingroup$

In his answer to a previous question, Sadeq Dousti recalled the following terminology:

  • $f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
  • $f(n) = 2^{n^{\Theta(1)}}$ is called exponential. (e.g. $2^n, 3^{n^4}$.)
  • $f(n) = 2^{n^{o(1)}}$ is called sub-exponential. (e.g. $2^{n^{1/n}}, n^{\log n}$.)

Is this standard terminology?

In particular, I am interested to know whether it is OK to call $2^{\sqrt{n}}$ and other functions in $2^{n^{\Theta(1)}}$ exponential or not.

Edited after 1st answer: Yes! The issue is when you have a $2^{\sqrt{n}}$ lower bound. Can you say that this is an "exponential" lower bound?

I am thinking here of a lower bound for a combinatorial value, not for some time complexity where one has standard definitions for $\mathsf{E}$ and $\mathsf{EXPTIME}$. I now realize I probably picked the wrong keywords.

$\endgroup$
  • 2
    $\begingroup$ cs.stackexchange.com/a/9814, en.m.wikipedia.org/wiki/Time_complexity $\endgroup$ – Kaveh May 17 '14 at 17:53
  • 1
    $\begingroup$ This question is neither research level question nor objective question to fit in SE Q&A sites. Also even for a subjective question, the context is not clear. All we know about the context of this problem is one sentence in the last paragraph. I'll be happy if someone who understand question context precisely and upvote it, he/she also can express it to me to make it clear. $\endgroup$ – Saeed May 18 '14 at 11:31
  • 1
    $\begingroup$ If the terminology is ambiguous (meaning not clearly unambiguous) in context, don't use it. $\endgroup$ – Jeffε May 23 '14 at 14:23
7
$\begingroup$

In general I agree with usul's summary: for upper bounds $2^{\sqrt{n}}$ is certainly at most exponential, and for lower bounds it's more context-dependent and less clear. Let me offer a couple more examples from different contexts, and provide the term "moderately exponential" for your consideration.

  • In the literature on graph isomorphism (which is typically dealing with upper bounds), $2^{\sqrt{n} poly(\log n)}$ (or even just $2^{n^c}$ with $c < 1$) is often referred to as moderately exponential (though I understand this term has a different meaning the context of exact algorithms for $\mathsf{NP}$-complete problems; for the relation between the two, see the Appendix to Paolo Codenotti's Thesis). In some sense one can view this as very humble, but not belittling, terminology: it recognizes how far such algorithms are from polynomial (or even quasi-polynomial) while still acknowledging that it represents quite significant progress over the brute force $n!$ algorithm, or even over singly-exponential ($2^{\Theta(n)}$) algorithms.

Referring to a $2^{\sqrt{n}}$ lower bound as moderately exponential could serve a similar function: humble enough to differentiate it from $2^{\Omega(n)}$ lower bounds, but significant enough to distinguish it from merely super-polynomial. On the other hand:

  • $2^{n^{O(1/d)}}$ lower bounds for depth $d$ Boolean circuits (or the corresponding Frege classes in proof complexity) are often referred to as "exponential lower bounds" to distinguish them from "merely" super-polynomial or quasi-polynomial lower bounds. However, as getting a $2^{\Omega(n)}$ lower bound in these situations can be quite important, the latter may sometimes be referred to as "strong exponential lower bounds" or sometimes "truly exponential lower bounds" to distinguish it from the "merely" $2^{n^{c}}$ lower bounds (with $c < 1$).

  • In the context of depth 4 algebraic circuits, $2^{\tilde{\Omega}(\sqrt{n})}$ lower bounds have been referred to as exponential. Note that getting any stronger lower bounds would separate $\mathsf{VP}$ from $\mathsf{VNP}$.

(Even in the context of Graph Isomorphism, I could see someone, perhaps informally, referring to a $2^{\sqrt{n}}$ lower bound as "exponential", since it would be understood that there is a $2^{O(\sqrt{n \log n})}$ upper bound so essentially no stronger exponential lower bound could be hoped for...)

$\endgroup$
4
$\begingroup$

I think these are all pretty standard, but context matters. I don't think there's a clear answer to your "particular" question, and I'll try to explain why.

Usually our usage of these terms comes from algorithm complexity. In terms of time complexity of algorithms, there are two definitions of exponential:

  • EXPTIME: $2^{n^{O(1)}}$. That is, $2$ raised to a polynomial in $n$.
  • E: $2^{O(n)}$. That is, $2$ raised to a function of $n$ that is at most linear.

Of course $2^{\sqrt{n}}$ fits in both classes. So the question is easily yes if we are just thinking about upper bounds: Naturally $2^{\sqrt{n}} < 2^n$ should be consider to lie in the class of exponential running times.

What I'm not so clear on is lower bounds. Specifically, I am not sure what a generally accepted interpretation of the following statement would be:

Deciding language $A$ requires exponential time.

(For example: If we show that $A$ requires time $2^{\sqrt{n}}$, should we say that $A$ requires exponential time?)

If we are thinking in the style of EXPTIME, I think we would say "yes": interpret the statement as saying that $A$ requires $2^{n^c}$ time for some $c > 0$. But thinking in the style of E, we would say no. For instance, the Exponential Time Hypothesis states informally that 3SAT requires exponential time, and formally it says that 3SAT requires $2^{cn}$ time for some $c$ (note the crucial difference!).

Because of this, I am not sure if there is a commonly accepted interpretation of the above statement. Ideally we would state more precisely what we mean when using the term, unless it's clear from context. Perhaps others can mention if they think one interpretation or the other is more "standard".

...

In summary: if $f(n) \leq 2^{\sqrt{n}}$, then $f$ is definitely at most exponential. But if $f(n) \geq 2^{\sqrt{n}}$, it is not clear to me whether we would say $f$ is at least exponential.

$\endgroup$
  • $\begingroup$ @DanielApon, I mean the signs as they are, but I'm not sure how to say it more clearly..... $\endgroup$ – usul May 18 '14 at 2:52
  • $\begingroup$ Fair enough -- seems fine to me $\endgroup$ – Daniel Apon May 18 '14 at 7:12
  • 4
    $\begingroup$ In general, it is better to avoid statements such as "A requires time ...", as it can be ambiguous (e.g., does every algorithm really need that time on every instance?). It is usually more precise to state negative results in the negative "There is no algorithm for A using time at most ..." $\endgroup$ – Daniel Marx May 18 '14 at 7:58
  • $\begingroup$ @DanielMarx, good point, definitely agree. But the issue could still come up with other wording, e.g. instead one might say in the intro to a paper, "there is an 'exponential' lower bound for A" and this could be unclear. $\endgroup$ – usul May 18 '14 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.