PSPACE

PSPACE とは計算けいさん複雑ふくざつ性せい理論りろんにおける複雑ふくざつ性せいクラスの一ひとつ、Polynomial SPACE の略りゃくである。

概要がいよう

PSPACE とはチューリングマシンによって多項式たこうしき領域りょういきで解とける問題もんだい、すなわち使用しようするテープの長ながさが問題もんだいのサイズの多項式たこうしきで収おさまる決定けってい問題もんだいのクラスのことである（処理しょりにかかる時間じかんは問とわない）。

多項式たこうしき時間じかんで解とける問題もんだいは当然とうぜんながらテープの使用しよう回数かいすうも問題もんだいのサイズの多項式たこうしきに比例ひれいするので P ⊆ PSPACE であることは自明じめいである。またNP ⊆ PSPACE であることも証明しょうめいされている。

このクラスに NP と同様どうようの概念がいねんを当あてはめたクラス、すなわち答こたえが与あたえられたときその検算けんざんが PSPACE になる NPSPACE というクラスを考かんがえることもできるが、1970年ねん ウォルター・サヴィッチ（Walter Savitch）のサヴィッチの定理ていりにより PSPACE = NPSPACE ということが証明しょうめいされた。

PSPACE完全かんぜん

NP完全かんぜんと同様どうように PSPACE に属ぞくする全すべての問題もんだいから多項式たこうしき時間じかん変換へんかん可能かのうであり、自みずからも PSPACE に属ぞくする問題もんだいを PSPACE完全かんぜん という。与あたえられた倉庫そうこ番ばんゲームが解かいを持もつかの判定はんてい（一般いっぱん倉庫そうこ番ばん問題もんだい）や、n×n マスのリバーシや五目並ごもくならべの与あたえられた局面きょくめんから先手せんてと後手ごてのどちらに必勝ひっしょう法ほうがあるかの判定はんていなどが、PSPACE完全かんぜんであることが知しられている。

その他たの特性とくせい

PSPACE は、交替こうたい性せいチューリング機械きかいで多項式たこうしき時間じかんで解とける問題もんだいの集合しゅうごうとしても定式ていしき化かできる。この場合ばあい、APTIME あるいは単たんに AP とも呼よぶ。

PSPACE は、IP と呼よばれる対話たいわ型がた証明しょうめい系けいで認識にんしきできる全ぜん言語げんごにも対応たいおうする。