Wiki gives two definitions for the NEXP complexity class:

  1. $ \mathsf{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(2^{n^k}) $

where $\mathsf{NTIME}(f(n))$ is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time $O(f(n))$.

  1. Using deterministic Turing machines as verifiers. A formal language ''L'' is in '''NEXPTIME''' if and only if there exist polynomials ''p'' and ''q'', and a deterministic Turing machine ''M'', such that
    • For all ''x'' and ''y'', the machine ''M'' runs in time $2^{p(|x|)}$ on input $(x,y)$
    • For all ''x'' in ''L'', there exists a string ''y'' of length $2^{q(|x|)}$ such that $M(x,y) = 1$
    • For all ''x'' not in ''L'' and all strings ''y'' of length $2^{q(|x|)}$, $M(x,y) = 0$

Is it obvious to see why these two definitions are equivalent? (if not, any way to prove they are equivalent?)

  • $\begingroup$ How do you define ​ NTIME(2^(n^k)) ? ​ ​ ​ ​ $\endgroup$ – user12859 Feb 2 '17 at 1:52
  • $\begingroup$ Updated the definitions. $\endgroup$ – Daniel Feb 2 '17 at 1:56
  • $\begingroup$ Do you already have the corresponding equivalence for the two definitions of NP? ​ ​ $\endgroup$ – user12859 Feb 2 '17 at 1:57
  • $\begingroup$ No, that's my question. But it's sorta implied by the Wikipage of NEXP. $\endgroup$ – Daniel Feb 2 '17 at 2:01
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… ​ ​ $\endgroup$ – user12859 Feb 2 '17 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.