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$ Commented Jan 9, 2019 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
    Commented Jan 9, 2019 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
    Commented Jan 9, 2019 at 13:08
  • $\begingroup$ Yes, I meant proper inclusion. $\endgroup$ Commented Jan 9, 2019 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$ Commented Jan 10, 2019 at 0:03

2 Answers 2

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.