NEXPTIME

In complexity theory , NEXPTIME (sometimes just NEXP ) stands for the complexity class of decision problems that can be accepted by a nondeterministic Turing machine in a time limited by (see Landau notation ) . Here is an arbitrary polynomial of the input size . In the DTIME therefore expressed notation applies: ${\displaystyle {\mathcal {O}}(2^{p(n)})}$ ${\displaystyle p(n)}$ ${\displaystyle n}$

${\displaystyle {\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left(2^{n^{k}}\right).}$

Relationship to other complexity classes

The following relationships are known:

NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME

Since according to the time hierarchy theorem, NP is a real subset of NEXPTIME and NC is a real subset of PSPACE, at least one of the above subset relationships must be real.

completeness

There are NEXPTIME complete issues. One example is the problem of determining whether two given regular expressions produce the same language, where the expressions only contain the operators union, concatenation, and doubling. In the usual notations of regular expressions, there would only be

• Association :, recognize or ,(x|y)xy
• Concatenation:, xyrecognizes xand then y, and
• Doubling:, x{2}detects xexactly twice,

allowed, where xand yare already under this scheme properly formed expressions or literals from the given alphabet. The characters (, |, )and {2}be perceived as not part of the literal alphabet. The doubling is just one more symbol, whereas the concatenation of xwith itself increases the size of the input significantly.

Web links

• NEXPTIME . In: Complexity Zoo. (English)

Individual evidence

1. ↑ Meyer, AR and L. Stockmeyer . The equivalence problem for regular expressions with squaring requires exponential space . 13th IEEE Symposium on Switching and Automata Theory , Oct 1972, pp. 125-129.