EXPTIME

ウィキペディア

EXPTIME

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/04/18 02:51 UTC 版)

EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2^p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。

DTIMEでは次のように表される。

${\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).$ 一覧・ カテゴリ