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
Article
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})
Connections
NP-complete
Entity
International Standard Book Number
Entity
algorithm
Entity
digital object identifier
Entity
International Standard Serial Number
Entity
JSTOR
Organization
formal language
Entity
Cambridge University Press
Entity
P versus NP problem
Entity
computational complexity theory
Entity
adjacency matrix
Entity
Hamiltonian path
Entity
NP
Entity
decision problem
Entity
time complexity
Entity
P
Entity
regular language
Entity
NP-hard
Entity
complexity class
Entity
non-deterministic Turing machine
Entity