1
$\begingroup$

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?
$\endgroup$
5
  • $\begingroup$ It’s knows that $\mathsf{NTIME}(f(n)) \subseteq \mathsf{DTIME}(2^{f(n)})$, and this implies that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. $\endgroup$ – Yuval Filmus Jan 9 '19 at 6:06
  • $\begingroup$ With "$\subset$" do you mean a proper inclusion or is equality allowed? (In the latter case, see Yuval Filmus' comment.) $\endgroup$ – dkaeae Jan 9 '19 at 8:43
  • $\begingroup$ 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. $\endgroup$ – chi Jan 9 '19 at 13:08
  • $\begingroup$ Yes, I meant proper inclusion. $\endgroup$ – Sebastian Oberhoff Jan 9 '19 at 22:54
  • $\begingroup$ $\subset$ is ambiguous: it's better to use $\subseteq$ for the "maybe equal" version and $\subsetneq$ (\subsetneq) for the "definitely not equal" version. $\endgroup$ – David Richerby Jan 10 '19 at 0:03
1
$\begingroup$

Upon reflection this is an easy consequence of the Time Hierarchy Theorem.

  • 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

So there's nothing new here.

$\endgroup$
1
$\begingroup$

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}\,$!

$\endgroup$

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.