# A question regarding definition of Deterministic Subexponential Time (SUBEXP)

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!

## 1 Answer

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.

• 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. – user777 Jul 13 '20 at 15:21
• This is just the usual set-theoretic notation. – Yuval Filmus Jul 13 '20 at 15:21