PSPACE
![本页使用了标题或全文手工转换](https://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
PSPACE | ||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() | ||||||||||||||||||||||||||||||||||||
|
PSPACE
形式 化 定 义
[编辑]如果规定 为至
PSPACE
与 其它复杂度 类的关系
[编辑]等 价定义
[编辑]复杂
PSPACE也等价于
PSPACE - 完全
[编辑]如果
其中,
PSPACE - Hard
[编辑]如果x
例 子
[编辑]围棋
参考 文献
[编辑]引用
[编辑]- ^ Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
- ^ Complexity Zoo, [1] (页面
存 档备份,存 于互联网档案 馆), accessed Mars 25, 2009 - ^ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
- ^ 萨维
奇 定理 - ^ 5.0 5.1 赫里斯托斯·帕帕
季 米 特 里 乌. "Games against Nature". "Journal of Computer and System Sciences". 1985, 31. - ^ 6.0 6.1
空 间层次 定理 - ^ Definition of Almost-PSPACE. PSPACE ⊆ PSPACE^A for every A.
- ^ Greg Kuperberg, Complexity Zoology: Active Inclusion Diagram, 2006, http://www.math.ucdavis.edu/~greg/zoology/diagram.xml (页面
存 档备份,存 于互联网档案 馆) - ^ K. W. Wagner. The complexity of combinatorial problems with succinct representation. Informatica. 1986, 23: 325–356.
- ^ 10.0 10.1 S. Toda. On the computational power of PP and ⊕P. FOCS 1989. 1989: 514–519.
- ^ QIP = PSPACE, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous arXiv:0907.4737 (July 2009)
- ^ "Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116."
- ^
未來 數學 家 的 挑戰 - 楊照崑 ;楊重駿 . [2013-05-11]. (原始 内容 存 档于2018-07-12).
来 源
[编辑]- Michael Sipser. Sections 8.2–8.3 (The Class PSPACE, PSPACE-completeness). Introduction to the Theory of Computation. PWS Publishing. 1997: 281–294. ISBN 0-534-94728-X.
- Christos Papadimitriou. 19: Polynomial space. Computational Complexity 1st. Addison Wesley. 1993: 455–490. ISBN 0-201-53082-1.
- Michael Sipser. 8: Space Complexity. Introduction to the Theory of Computation 2nd. Thomson Course Technology. 2006. ISBN 0-534-95097-3.
- Arora, Sanjeev; Barak, Boaz. Computational complexity. A modern approach. Cambridge University Press. 2009. ISBN 978-0-521-42426-4. Zbl 1193.68112.
- Papadimitriou, Christos. 19: Polynomial space. Computational Complexity 1st. Addison Wesley. 1993: 455–490. ISBN 0-201-53082-1.
- Sipser, Michael. 8: Space Complexity. Introduction to the Theory of Computation 2nd. Thomson Course Technology. 2006. ISBN 0-534-95097-3.
外部 链接
[编辑]- Lecture slides on space complexity From University of Toronto
- Lecture slides on space complexity From Princeton University
- Complexity Zoo: PSPACE(页面
存 档备份,存 于互联网档案 馆)
|