NEXPTIME

計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2^p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。

NTIMEの記法では以下のように表される。

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

重要な NEXPTIME完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合はNP完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる^[1]。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である^[2]。

なお、P=NP であった場合、NEXPTIME=EXPTIME となることに注意されたい。