NEXPTIME
Sign in to saveIn computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^{n^{O(1).
~5 min read
Encyclopedic overview
8 sectionsContents
- Alternative characterizations
- NEXPTIME-complete
- Examples of NEXPTIME-complete problems
- Succinct problems
- Logic
- Games
- See also
- References
In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^{n^{O(1)}}.
In terms of NTIME, \mathsf{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(2^{n^k})
Excerpted from Wikipedia’s “NEXPTIME” article, available under the CC BY-SA 4.0 licence.