スペース

コンピュータサイエンスにおける未解決の問題:

⁠ ⁠${\displaystyle {\mathsf {P{\overset {?}{=}}PSPACE}}}$

(コンピュータサイエンスにおける未解決の問題)

計算複雑性理論において、PSPACE は、多項式量の空間を使用してチューリング マシンで解決できるすべての決定問題の集合です。

入力サイズnの関数fに対して、チューリングマシンでO ( f ( n ))の空間を使用して解くことができるすべての問題の集合をSPACE( f ( n ))と表すと、PSPACEは次のように正式に定義できます^[1]

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {SPACE}}(n^{k}).}$

チューリングマシンを非決定的にしても、追加のパワーは追加されないことが判明しました。サビッチの定理により、^{[2] NPSPACE は PSPACE と同等です。これは基本的に、決定性チューリングマシンは、それほど多くのスペースを必要とせずに}非決定性チューリングマシンをシミュレートできるためです(ただし、はるかに多くの時間がかかります)。^[3] また、 PSPACE のすべての問題の補数も PSPACE に含まれており、co-PSPACE = PSPACE であることを意味します。^[要出典]

PSPACE と複雑性クラスNL、P、NP、PH、EXPTIME、EXPSPACEの間には、次の関係が知られています(⊊ は厳密な包含を表すので、⊈ と混同しないように注意してください)。

${\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}}$

3 行目から、1 行目と 2 行目の両方で、少なくとも 1 つの集合包含が厳密でなければならないことがわかりますが、どれが厳密であるかはわかりません。すべてが厳密であると広く疑われています。

3 行目の包含関係は両方とも厳密であることが知られています。1 つ目は、直接対角化 (空間階層定理、NL ⊊ NPSPACE) と、サビッチの定理により PSPACE = NPSPACE であるという事実から導かれます。2 つ目は、単純に空間階層定理から導かれます。

PSPACE で最も難しい問題は、PSPACE 完全問題です。PSPACEに該当すると思われるが NP には該当しない問題の例については、 PSPACE 完全を参照してください。

クラス PSPACE は、演算union、complementation、およびKleene starに関して閉じています。

PSPACEの別の特徴付けは、交代チューリングマシンによって多項式時間で決定可能な問題の集合であり、APTIMEまたは単にAPと呼ばれることもあります。^[4]

記述的複雑性理論による PSPACE の論理的特徴は、推移閉包演算子を追加することで2 階論理で表現できる問題の集合であるということです。完全な推移閉包は必要ありません。可換推移閉包とさらに弱い形式で十分です。この演算子の追加が、 PSPACE とPH を(おそらく) 区別するものです。

複雑性理論の主な結果は、PSPACE が、クラスIPを定義する特定の対話型証明システムによって認識可能なすべての言語として特徴付けられることです。このシステムでは、文字列がその言語にあることをランダム化された多項式時間検証者に納得させようとする全能の証明者がいます。文字列がその言語にある場合は高い確率で検証者を納得させることができるはずですが、文字列がその言語にない場合は低い確率を除いて納得させることはできません。

PSPACEは量子複雑性クラスQIPとして特徴付けられる。^[5]

_{PSPACEはP CTC（}閉じた時間的曲線を使用する古典コンピュータで解ける問題）^[6]やBQP _CTC （閉じた時間的曲線を使用する量子コンピュータで解ける問題^）[7]にも等しい。

言語BがPSPACE 完全とは、それが PSPACE にあり、かつ PSPACE 困難である場合に成り立ちます。つまり、すべてのA ∈ PSPACE に対して、であり、 はAからBへの多項式時間の多対一還元が存在することを意味します。PSPACE 完全問題は PSPACE で最も困難な問題であるため、PSPACE 問題の研究において非常に重要です。PSPACE 完全問題の簡単な解を見つけることは、PSPACE の他のすべての問題に対する簡単な解が得られることを意味します。なぜなら、すべての PSPACE 問題は PSPACE 完全問題に還元できるからです。^[8]${\displaystyle A\leq _{\text{P}}B}$${\displaystyle A\leq _{\text{P}}B}$

PSPACE完全問題の例としては、量化ブール式問題（通常QBFまたはTQBFと略される。Tは「真」を意味する）がある。^[8]

• Arora, Sanjeev ; Barak , Boaz (2009).計算複雑性。現代的なアプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4.ZBL1193.68112  。​
• シプサー、マイケル(1997)。計算理論入門。PWS 出版。ISBN 0-534-94728-X。セクション8.2–8.3（クラスPSPACE、PSPACE完全性）、pp. 281–294。
• パパディミトリウ、クリストス(1993)。計算複雑性(第 1 版)。アディソン ウェスリー。ISBN 0-201-53082-1。第19章: 多項式空間、pp. 455–490。
• シプサー、マイケル(2006)。計算理論入門(第 2 版)。トムソン コース テクノロジー。ISBN 0-534-95097-3。第8章: 空間の複雑さ
• 複雑性動物園: PSPACE