PSPACE

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

\mbox{SPACE}(s(n)) đượ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ớ s(n), trong đó s là một hàm số của n. Định nghĩa **PSPACE** là

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

**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ù 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

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 \subsetneq khác với \not\subseteq):

:\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}
:\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}
:\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}

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, \mbox{NL} \subsetneq \mbox{NPSPACE}) và \mbox{PSPACE} = \mbox{NPSPACE} 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]]**.

## 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 \in PSPACE, A \leq_p B, trong đó A \leq_p 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

* 
*  Phần 8.2&ndash;8.3 (Lớp PSPACE, PSPACE-đầy đủ), tr.&nbsp;281&ndash;294.
*  Chương 19: Không gian đa thức, tr.&nbsp;455&ndash;490.
*  Chương 8: Độ phức tạp không gian

## Liên kết ngoài
* Bài giảng về độ phức tạp không gian ở University of Toronto 
* Bài giảng về độ phức tạp không gian ở Princeton University