NEXPTIME

ウィキペディア

NEXPTIME

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/06/29 17:54 UTC 版)

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

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

${\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(2^{n^{k}})$ 一覧・ カテゴリ