NSPACE

提供: miniwiki
2018/8/19/ (日) 17:31時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

計算複雑性理論において、複雑性クラス NSPACE(f(n)) とは、非決定性チューリング機械で領域 O(f(n)) と無制限の時間で解ける決定問題の集合である。DSPACEの非決定性バージョンである。

複雑性クラス NPSPACENSPACE を使って以下のように定義できる。

[math]\mbox{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)[/math]

脚注


テンプレート:複雑性クラス