PSPACE

PSPACE：多項式領域で解ける問題のクラス

計算複雑性理論において、PSPACE（Polynomial SPACE）は、チューリングマシンを用いて多項式領域で解ける決定問題の集合を表す重要な複雑性クラスです。ここで、多項式領域とは、問題の入力サイズnに対して、使用するテープの長さがnの多項式で抑えられることを意味します。処理時間については制限されません。

PSPACEの包含関係

PSPACEは、他の複雑性クラスと密接な関係を持っています。まず、多項式時間で解ける問題のクラスPは、PSPACEに含まれます（P ⊆ PSPACE）。これは、多項式時間で解ける問題は、必然的に多項式領域しか使用しないためです。また、非決定性多項式時間で解ける問題のクラスNPも、PSPACEに含まれることが証明されています（NP ⊆ PSPACE）。

さらに、NPと同様の概念をPSPACEに適用したクラスとして、NPSPACEが考えられます。これは、答えが与えられたとき、その検証がPSPACEで解ける問題のクラスです。しかし、1970年にWalter Savitchによって証明されたサヴィッチの定理により、PSPACE = NPSPACEであることが示されました。これは、NPSPACEの問題は、本質的にPSPACEの問題と同じであることを意味しています。

PSPACE完全問題

NP完全問題と同様に、PSPACE完全問題も定義されます。PSPACE完全問題は、以下の2つの条件を満たす問題です。

1. PSPACEに属する。
2. PSPACEに属する全ての問題が多項式時間でこの問題に帰着できる。

PSPACE完全問題は、PSPACEの中でも最も難しい問題のクラスであり、PSPACE完全問題の一つを多項式時間で解くアルゴリズムが見つかれば、全てのPSPACEの問題が多項式時間で解けることになります。

代表的なPSPACE完全問題として、一般倉庫番問題（与えられた倉庫番ゲームが解を持つかの判定）、n×nマスのリバーシや五目並べの必勝法判定などが挙げられます。これらのゲームは、状態数が指数関数的に増加するため、単純な探索アルゴリズムでは多項式時間で解くことができません。

PSPACEの他の特性

PSPACEは、交替性チューリングマシンを用いて多項式時間で解ける問題の集合としても定義できます。交替性チューリングマシンは、存在と全称の量子化子を交互に用いて計算を行うモデルです。この定義におけるPSPACEは、APTIME（Alternating Polynomial TIME）または単にAPとも呼ばれます。

また、PSPACEは、IP（Interactive Proof System）と呼ばれる対話型証明系で認識できる全言語にも対応します。IPは、多項式時間内で動作する検証者と、無制限の計算能力を持つ証明者の間の対話によって問題の正しさを検証するモデルです。PSPACE = IPという関係は、計算複雑性理論において重要な結果です。

まとめ

PSPACEは、計算複雑性理論における重要な複雑性クラスであり、多項式領域で解ける決定問題の集合を表します。P、NPといった他のクラスとの包含関係、PSPACE完全問題の存在、そして交替性チューリングマシンや対話型証明系との関連性など、PSPACEは計算機科学の様々な分野に影響を与えています。今後の研究によって、PSPACEの性質や関連するクラスとの関係性がより深く解明されることが期待されます。

もう一度検索