計算 複雜度 理論 에서 PSPACE 는 決定論的 튜링 機械 나 非決定論的 튜링 機械 가 時間은 얼마든지 쓸 수 있고, 空間은 다항 空間만 써서 풀 수 있는 判定 問題 들의 集合이다. 社備置 整理 에 따르면 PSPACE는 NSPACE 와 같기 때문에 튜링 機械가 決定論的이든 非決定論的이든 相關 없다.

文脈-敏感 言語 가 PSPACE 의 眞部分集合이다. 複雜度 種類 NL , P , NP , PSPACE , EXPSPACE 가 갖는 關係는 이렇다:

${\displaystyle {\mathsf {NL}}\subseteq {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}}$

${\displaystyle {\mathsf {NL}}\subsetneq {\mathsf {PSPACE}}\subsetneq {\mathsf {EXPSPACE}}}$

첫째 줄에 ${\displaystyle \subseteq }$ ( 部分集合 ) 畿湖가 세 個 있다. 셋 中 하나는 ${\displaystyle \subsetneq }$與野 하는데, 正確히 어느 것이 그런지는 알려진 바 없다. 수많은 사람들이 셋 모두 ${\displaystyle \subsetneq }$라고 推測하고 있다. P-NP 問題 (두 番째 ${\displaystyle \subseteq }$가 ${\displaystyle \subsetneq }$인지 아닌지 묻는 問題)에 對한 解法에는 賞金 百萬 달러 가 걸려 있다.

PSPACE 에서 가장 어려운 問題들을 PSPACE-完全 이라고 한다. PSPACE 이고 NP 는 아닐 것으로 豫想되는 問題들을 알고 싶으면 PSPACE-完全 을 보라.

다른 定義 [ 編輯 ]

PSPACE 를 交代 튜링 機械 가 다항 時間에 判定할 수 있는 問題의 集合으로 定義하기도 한다. APTIME 아니면 그냥 AP 라고도 한다.

論理學에 바탕을 둔 正義는, 二次 論理 에 推移 닫힘 演算을 더해서 表現할 수 있는 問題의 集合을 PSPACE 라고 한다. 完全한 推移 닫힘일 必要는 없다. 可換 推移 肺胞나 더 若干 形態도 充分하다. 이 演算子를 追加함으로써 PSPACE 와 PH 를 區分할 수 있(을지도 모르)게 된다.

複雜度 理論의 重要한 結果 中 하나는, PSPACE 를 特定 對話型 證明 體系 가 받아들일 수 있는 모든 言語로 특징지을 수 있다는 것이다. 이는 IP 를 定義하는 特徵이기도 하다. 이 體系에는 確率的 다항 時間 檢證者가 주어진 言語에 어떤 文字列이 들어간다고 確信하게 하는 全能한 證明者가 있다. 文字列이 그 言語에 들어간다면, 檢證者를 높은 確率로 確信시킬 수 있어야 한다. 그러나 들어가지 않는다면 낮은 確率로 例外가 생기는 境遇를 빼고는 確信시킬 수 없어야 한다.

參考 文獻 [ 編輯 ]

• (英語) 複雜度 動物園 PSPACE 우리
• 마이클 사이프저 (1997). 〈8.2-8.3 (複雜度 種類 PSPACE, PSPACE-完全( The Class PSPACE, PSPACE-completeness ))〉. 《Introduction to the Theory of Computation》 (英語). PWS Publishing. 281 -294쪽. ISBN   0-534-94728-X .  
• 크리스토스 파파디미트리禹 (1993). 〈19: 다항 空間( Polynomial space )〉. 《Computational Complexity》 (英語) 1板. Addison Wesley. 455-490쪽. ISBN   0-201-53082-1 .   CS1 管理 - 追加 文句 ( 링크 )