Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

7
  • 5
    $\begingroup$ It's good to clarify what you mean by sub-exponential. See also cs.stackexchange.com/questions/9813/… $\endgroup$ Commented Jun 21, 2020 at 4:20
  • 1
    $\begingroup$ If the author means subexponential as in III. from the resource in the above comment, then I have a feeling some studied Exponential-time Complete problems would also meet the criteria. $\endgroup$ Commented Jun 21, 2020 at 4:23
  • 4
    $\begingroup$ Yes, this is very nonstandard. This makes $2^n$ subexponential. $\endgroup$ Commented Jun 23, 2020 at 12:08
  • $\begingroup$ @DominicvanderZypen $\frac1me^n=\Omega(2^n)$. $\endgroup$ Commented Jun 23, 2020 at 12:46
  • 1
    $\begingroup$ The new definition is hard to decipher, but is actually equivalent to just $f(n)=2^{o(n)}$. Why don’t you write it that way? (And while this is not nonstandard, in complexity theory this definition is less common and less convenient than the more natural definition $f(n)=2^{n^{o(1)}}$, which is robust wrt polynomial changes in the representation of the input or in the parameter to specify the problem. E.g., according to your definition, brute force $2^{O(|V|)}$ algorithms for the maximum independent set and similar graph problems are “subexponential” as the size of the input is $|V|^2$.) $\endgroup$ Commented Jun 24, 2020 at 6:59