NSPACE
計算複雑性理論において、複雑性クラス NSPACE(f(n)) とは、非決定性チューリング機械で領域 O(f(n)) と無制限の時間で解ける決定問題の集合である。DSPACEの非決定性バージョンである。
複雑性クラス NPSPACE は NSPACE を使って以下のように定義できる。
NPSPACE = ⋃ k ∈ N NSPACE ( n k ) {\displaystyle {\mbox{NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})}