エヌスペース

計算複雑性理論において、非決定性空間またはNSPACE は、非決定性チューリングマシンのメモリ空間を記述する計算リソースです。これは、 DSPACEの非決定性版です。

NSPACEという尺度は、非決定性チューリングマシンによって解が決定できる複雑性クラスを定義するために使用されます。複雑性クラスNSPACE( f ( n ))は、空間O ( f ( n ))を使用して非決定性チューリングマシンMによって解決できる決定問題の集合です。ここで、nは入力の長さです。^[1]

いくつかの重要な複雑性クラスは、 NSPACEの観点から定義できます。これには次のものが含まれます。

• REG = DSPACE( O (1)) = NSPACE( O (1))、ここでREGは正規言語のクラスです（非決定性は定数空間ではパワーを追加しません）。
• NL = NSPACE( O (log  n ))
• CSL = NSPACE( O ( n ))、ここでCSLは文脈依存言語のクラスである。
• P空間= NP空間 =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$
• EXP空間= NEXPSPACE =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

インマーマン・シェレプセニの定理は、NSPACE( s ( n )) はすべての関数s ( n ) ≥ log nに対して補関数に対して閉じていることを述べています。

さらに一般化したものには、交互チューリング マシンで定義される ASPACE があります。

NSPACE は、決定論的チューリングマシン上のメモリ空間のクラスであるDSPACEの非決定論的対応物です。まず定義により、次にSavitch の定理により、次のようになります。

${\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].}$

NSPACE は、次の定理によって 決定論的チューリング マシンの時間計算量を決定するためにも使用できます。

言語L^が空間S ( n )(ただしS ( n )≥logn )内で非決定論的TMによって決定される場合、Lが決定論的TMによって時間O ( CS ^{( n )} )で決定されるような定数Cが存在する。^[2]

DSPACEによる空間計算量の測定は、実際のコンピュータが特定のアルゴリズムを使用して特定の計算問題を解くために必要なメモリの総量を表すため便利です。その理由は、DSPACE は実際のコンピュータを表すことができる決定論的チューリング マシンで使用される空間計算量を記述するためです。一方、NSPACE は実際のコンピュータを表すのに役立たない非決定論的チューリング マシンの空間計算量を記述します。このため、NSPACE の実用性は現実世界のアプリケーションに限定されています。

• 複雑性動物園:NSPACE(f(n))。