# Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

I think I'm able to prove NTIME($$n^\alpha$$) $$\subset$$ EXPTIME for arbitrary $$\alpha$$.

• Is this a new result?
• If it was, would there be a way to deduce NP $$\subset$$ EXPTIME from it?
• It’s knows that $\mathsf{NTIME}(f(n)) \subseteq \mathsf{DTIME}(2^{f(n)})$, and this implies that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. Commented Jan 9, 2019 at 6:06
• With "$\subset$" do you mean a proper inclusion or is equality allowed? (In the latter case, see Yuval Filmus' comment.) Commented Jan 9, 2019 at 8:43
• Assuming strict inclusion, I'd lean towards "no" for the second question. From $A \subset X$ and $B \subset X$ we can only conclude the loose inclusion $A \cup B \subseteq X$, and not the stricter $A \cup B \subset X$, in general.
– chi
Commented Jan 9, 2019 at 13:08
• Yes, I meant proper inclusion. Commented Jan 9, 2019 at 22:54
• $\subset$ is ambiguous: it's better to use $\subseteq$ for the "maybe equal" version and $\subsetneq$ (\subsetneq) for the "definitely not equal" version. Commented Jan 10, 2019 at 0:03

• NTIME$$(n^\alpha) \subseteq$$ TIME$$\left(2^{n^\alpha}\right)$$ by brute force
• TIME$$\left(2^{n^\alpha}\right) \subset$$ TIME$$\left(2^{n^{2\alpha}}\right)$$ by the Time Hierarchy Theorem
• TIME$$\left(2^{n^{2\alpha}}\right) \subseteq$$ EXPTIME obviously
As you've already shown, $$\mathrm{NTIME}[n^\alpha]\subsetneq\mathrm{EXPTIME}$$ isn't new, as it follows easily from the time hierarchy theorem.
Furthermore, the fact that, for some class $$X$$, $$\mathrm{NTIME}[n^\alpha]\subsetneq X$$ for all $$\alpha$$ doesn't imply that $$\mathrm{NP}\subsetneq X$$. For example, the time hierarchy theorem tells us $$\mathrm{NTIME}[n^\alpha]\subsetneq\mathrm{NP}$$ for all $$\alpha$$ but that certainly doesn't imply that $$\mathrm{NP}\subsetneq\mathrm{NP}\,$$!