NEXPTIME

In complexity theory is NEXPTIME (sometimes just NEXP ) for the complexity class of decision problems that can be accepted by a nondeterministic Turing machine in a limited (see Landau notation) time. Here is an arbitrary polynomial of the input length. Expressed in DTIME notation applies:

Relation to other complexity classes

The following relations are known:

As is true for the time hierarchy theorem that NP is a proper subset of NEXPTIME, and NC is a proper subset of PSPACE, at least one of the above subset relationships must be genuine.