NSPACE

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "NSPACE" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年4月)

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

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

${\displaystyle {\mbox{NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})}$

この節の加筆が望まれています。

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ