# Equivalence between the two definitions of NEXPTIME complexity class

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?)

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