NSPACE

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

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

脚注[編集]

[ヘルプ]