1
$\begingroup$

First Look at the definition of SUBEXP from Complexity Zoo:

SUBEXP: (Deterministic Subexponential-Time) The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm used may vary with $\epsilon$.) or it can be written as: SUBEXP = $\bigcap_{\epsilon>0}$DTIME$(2^{n^\epsilon})$.

So, I bring the definition of EXP which is:

EXP = $\bigcup_{k\geq 1}$DTIME$(2^{n^k})$

The definition of EXP is clear, since it includes all polynomial of n to the power of 2. (e.g. $2^{n^{30}}$ or $100^{n^{99}}$ etc.)

First question: what is domain of $\epsilon$? I guess it is between 0 and 1 but it didn't specify in the definition. Is it usual that when we have $\epsilon$ then it means between 0 and 1.

Second question: Now, in case of SUBEXP, it is not clear how the definition is about the intersection? I mean, Shouldn't be written as following: $\bigcup_{1>\epsilon>0}$DTIME$(2^{n^\epsilon})$. For example by definition above what is the intersection of: $2^{n^{0.01}} \bigcap 2^{n^{0.02}} ?$

Third question: There are two definition of SUBEXP in wikipedia, Is there definition that take over all subexponential or we don't since this is why we have two definitions.

Thank you!

$\endgroup$
1
$\begingroup$

In the definition of SUBEXP, $\epsilon$ ranges over all positive reals. But you get the same definition if you ask that $\epsilon < \epsilon_0$, for an $\epsilon_0>0$ of your choice; if you ask that $\epsilon$ be rational; if you only go over $\epsilon = 1/n$; and so on. This is because DTIME is monotone: if $f \leq g$ then $\mathsf{DTIME}(f) \subseteq \mathsf{DTIME}(g)$.

An alternative definition of SUBEXP would be: $$ \mathsf{SUBEXP} = \bigcup_{g(n) = o(1)} \mathsf{DTIME}(2^{n^{g(n)}}), $$ often denoted simply by $\mathsf{DTIME}(2^{n^{o(1)}})$.

Some examples: $\mathsf{P} \subseteq \mathsf{SUBEXP}$; a function which can be computed in time $2^{n^{1/\log\log n}}$ is in $\mathsf{SUBEXP}$; and a function which can be computed in time $2^{\log^{10} n}$ is in $\mathsf{SUBEXP}$.

In contrast, a function which can be computed in time $2^{n^{1/10}}$ is not necessarily in $\mathsf{SUBEXP}$ (and by the time hierarchy theorem, there is such a function which lies outside $\mathsf{SUBEXP}$).

A function in $\mathsf{DTIME}(2^{n/\log n})$ lies in SUBEPT but not necessarily in SUBEXP.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Yuval so much. It took me a while to understand this issue. It seems that the intersections $\bigcap_{\epsilon>0}$DTIME$(2^{n^\epsilon})$ means everything that is less than $2^{n^\epsilon}$ for any positive real number $\epsilon$. I wonder why we use $\bigcap$? It is not at all clear that it says less than $2^{n^\epsilon}$. I can defined SUBEXP as following: $2^{n^{\frac{1}{f(n)}}}$ where $f(n)=\Omega(n)$, for example: $f(n)=n, n^2, 2^n, log n$, etc. Thank you again Yuval. $\endgroup$ – user777 Jul 13 at 15:21
  • 1
    $\begingroup$ This is just the usual set-theoretic notation. $\endgroup$ – Yuval Filmus Jul 13 at 15:21

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.