Xem mã nguồn của PSPACE

{{vấn đề mở|khoa học máy tính|Có phải '''P''' {{=}} '''PSPACE''' ?}}
<!--
{{Hộp thông tin lớp độ phức tạp
|lớp=PSPACE
|ảnh=[[Tập tin:Complexity subsets pspace.svg|200px]]
|long-name=Polynomial space
|description=
|wheredefined=
|external-urls=[http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pspace Complexity Zoo]
|lớp đầy đủ=[[PSPACE-complete]]
|lớp phần bù=''self''
|tập hợp cha thật sự=[[EXPSPACE]]<ref name="spacehierarchy">[[định lý cấp bậc không gian]]</ref>
|tập hợp cha=[[EXPTIME]], [[RG (độ phức tạp)|RG]], [[QPSPACE]]<ref name="zoodiagram">Greg Kuperberg, Complexity Zoology: Active Inclusion Diagram, 2006, http://www.math.ucdavis.edu/~greg/zoology/diagram.xml</ref>
|bằng=AP,<ref>[http://portal.acm.org/citation.cfm?id=322243&coll=Portal&dl=ACM&CFID=60283170&CFTOKEN=44928981 Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation'], Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.</ref> [[BPPSPACE]],<ref>Complexity Zoo, [http://qwiki.stanford.edu/wiki/Complexity_Zoo:A#almostpspace]. Truy cập Mars 25, 2009.</ref> [[IP (complexity)|IP]],<ref>Adi Shamir. [http://portal.acm.org/citation.cfm?doid=146585.146609 IP = PSPACE]. ''Journal of the ACM'', volume 39, issue 4, p.869&ndash;877. October 1992.</ref> NPSPACE,<ref>[[Savitch's theorem]]</ref> [[PPSPACE]],<ref name="papadimitriou85games">{{chú thích tạp chí|author=[[Christos Papadimitriou]]|title=Games against Nature | journal="Journal of Computer and System Sciences"|volume=31|year=1985}}</ref> [[SAPTIME]]<ref name="papadimitriou85games"/>
|liên quan=[[PTIME]]
|không bằng=P-close, P/log
|tập hợp con=[[CH (độ phức tạp)|CH]],<ref name="wagner85complexity">{{chú thích tạp chí|author=K. W. Wagner|title=The complexity of combinatorial problems with succinct representation|journal=Informatica|volume=23|year=1986|pages=325–356}}</ref> P^[[PP (complexity)|PP]],<ref name="toda89onthe">{{chú thích tạp chí|author=S. Toda|title=On the computational power of PP and ⊕P|journal=FOCS 1989|year=1989|pages=514–519}}</ref> P^[[Sharp-P|#P]],<ref name="toda89onthe"/> [[QSZK]], RG[1]
|proper-subsets=[[NL (complexity)|NL]]<ref name="spacehierarchy"/>
|properties=Syntactic
|low-with=''self''
|low-for=''self''
|closed-reductions=[[Polynomial-time Turing reduction|Poly-time]]
|closed-operations=
|canonical-problems=[[QSAT]]
|models=[[Alternating Turing machine]], [[Turing machine]]
}}
-->

Trong [[lý thuyết độ phức tạp tính toán]], '''PSPACE''' là tập hợp các [[bài toán quyết định]] giải được bằng máy Turing trong không gian/bộ nhớ [[đa thức]].

== Định nghĩa ==

<math>\mbox{SPACE}(s(n))</math> được định nghĩa là tập hợp tất cả các bài toán quyết định giải được bằng [[máy Turing]] trong bộ nhớ <math>s(n)</math>, trong đó <math>s</math> là một hàm số của <math>n</math>. Định nghĩa '''PSPACE''' là

<math>\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)</math>

'''PSPACE''' là tập hợp cha thực sự của tập hợp các [[ngôn ngữ phụ thuộc ngữ cảnh]].

Việc cho phép máy Turing sử dụng [[thuật toán không đơn định]] không làm thay đổi lớp độ phức tạp này. Theo [[định lý Savitch]], NPSPACE đúng bằng PSPACE, do máy Turing đơn định có thể giả lập máy Turing không đơn định mà bộ nhớ không cần tăng lên quá nhiều (dù thời gian cần dùng có thể tăng lên nhiều). Ngoài ra [[Phần bù (độ phức tạp)|phần bù]] của các ngôn ngữ trong PSPACE cũng nằm trong PSPACE, nên co-PSPACE = PSPACE.

== Liên hệ với các lớp độ phức tạp khác ==
[[Hình:Complexity subsets pspace.svg|300px|nhỏ|phải|Liên hệ giữa một số lớp độ phức tạp]]
Cho đến nay, các liên hệ sau giữa '''PSPACE''' và các lớp độ phức tạp '''[[NL (độ phức tạp)|NL]]''', '''[[P (độ phức tạp)|P]]''', '''[[NP (độ phức tạp)|NP]]''', '''[[PH (độ phức tạp)|PH]]''', '''[[EXPTIME]]''' and '''[[EXPSPACE]]''' đã được chứng minh (chú ý rằng <math>\subsetneq</math> khác với <math>\not\subseteq</math>):

:<math>\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}</math>
:<math>\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}</math>
:<math>\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}</math>

Ngoài ra người ta cũng đã chứng minh trong các quan hệ trong dòng một và dòng hai ở trên, tồn tại ít nhất một quan hệ tập hợp cha-con là chặt.

Các liên hệ ở dòng ba là chặt, có thể chứng minh bằng phương pháp chéo hóa ([[định lý cấp bậc không gian]], <math>\mbox{NL} \subsetneq \mbox{NPSPACE}</math>) và <math>\mbox{PSPACE} = \mbox{NPSPACE}</math> theo [[định lý Savitch]].

Các bài toán khó nhất trong '''PSPACE''' là các bài toán '''PSPACE-đầy đủ'''.

== Các định nghĩa tương đương ==

Một định nghĩa tương đương của '''PSPACE''' là tập hợp các bài toán quyết định được bởi [[máy Turing luân phiên]] trong thời gian đa thức, ký hiệu là '''APTIME''' hay '''AP'''.

Một định nghĩa khác của '''PSPACE''' từ lý thuyết [[độ phức tạp mô tả]] là tập hợp các bài toán biểu diễn được trong [[lôgic bậc hai]] bổ sung thêm toán tử [[bao đóng bắc cầu]]. Việc thêm toán tử này (có thể) là điểm khác biệt giữa '''PSPACE''' và '''[[PH (độ phức tạp)|PH]]'''.

Một kết quả lớn trong lý thuyết độ phức tạp tính toán là '''PSPACE''' chính là tập hợp các ngôn ngữ giải được bởi các [[hệ chứng minh tương tác]] dùng để định nghĩa lớp '''[[IP (độ phức tạp)|IP]]'''. Trong hệ này, một người chứng minh toàn năng cố gắng thuyết phục một người kiểm chứng có khả năng thực thi thuật toán ngẫu nhiên trong thời gian đa thức rằng một xâu ký tự nằm trong ngôn ngữ cần xem xét. Nếu xâu ký tự thật sự nằm trong ngôn ngữ đó thì người chứng minh có thể thuyết phục được với xác suất cao. Ngược lại, nếu xâu ký tự không nằm trong ngôn ngữ thì người chứng minh chỉ có thể thuyết phục thành công với xác suất thấp.

'''PSPACE''' cũng bằng lớp độ phức tạp lượng tử '''[[QIP (độ phức tạp)|QIP]]'''.<ref>QIP = PSPACE, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, [[John Watrous (computer scientist)|John Watrous]] arXiv:0907.4737 (July 2009)</ref>

== PSPACE-đầy đủ==
{{chính|PSPACE-đầy đủ}}
Ngôn ngữ ''B'' là ''[[PSPACE-đầy đủ]]'' nếu nó nằm trong PSPACE và là PSPACE-khó, nghĩa là với mọi A <math>\in</math> PSPACE, A <math>\leq_p</math> B, trong đó A <math>\leq_p</math> B nghĩa là tồn tại một thuật toán thời gian đa thức quy mỗi trường hợp trong A về một trường hợp trong B. Việc nghiên cứu các bài toán PSPACE-đầy đủ là rất quan trọng cho việc nghiên cứu PSPACE do chúng là những bài toán khó nhất trong PSPACE. Nếu tồn tại một lời giản đơn giản cho một bài toán PSPACE-đầy đủ thì mọi bài toán trong PSPACE đều có lời giải đơn giản do chúng đều có thể quy về bài toán PSPACE-đầy đủ.

==Tham khảo==
{{Tham khảo}}
* {{CZoo|PSPACE|P#pspace}}
* {{chú thích sách|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | isbn = 0-534-94728-X}} Phần 8.2&ndash;8.3 (Lớp PSPACE, PSPACE-đầy đủ), tr.&nbsp;281&ndash;294.
* {{chú thích sách|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = thứ 1| isbn = 0-201-53082-1}} Chương 19: Không gian đa thức, tr.&nbsp;455&ndash;490.
* {{chú thích sách|author = Michael Sipser | year = 2006 | title = Introduction to the Theory of Computation | publisher = Thomson Course Technology| edition = thứ 2| isbn = 0-534-95097-3}} Chương 8: Độ phức tạp không gian

==Liên kết ngoài==
* [http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt Bài giảng về độ phức tạp không gian ở University of Toronto] {{Webarchive|url=https://web.archive.org/web/20110607195631/http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt |date=2011-06-07 }}
* [http://www.cs.princeton.edu/~wayne/kleinberg-tardos/09pspace.pdf Bài giảng về độ phức tạp không gian ở Princeton University] {{Webarchive|url=https://web.archive.org/web/20060916231137/http://www.cs.princeton.edu/~wayne/kleinberg-tardos/09pspace.pdf |date=2006-09-16 }}

{{Lớp độ phức tạp}}

[[Thể loại:Lớp độ phức tạp]]