PSPACE คืออะไร? ทำความเข้าใจคลาสความซับซ้อนของพื้นที่หน่วยความจำ

ในทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) PSPACE คือเซตของปัญหาการตัดสินใจ (Decision Problems) ทั้งหมดที่สามารถแก้ไขได้โดยใช้เครื่องจักรทัวริง (Turing machine) โดยใช้พื้นที่หน่วยความจำในปริมาณที่เป็นพหุนาม (Polynomial amount of space) เมื่อเทียบกับขนาดของอินพุต

คำจำกัดความอย่างเป็นทางการ

หากเรากำหนดให้

คือเซตของปัญหาทั้งหมดที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงที่ใช้พื้นที่

สำหรับฟังก์ชัน

ของขนาดอินพุต

เราสามารถนิยาม

ได้อย่างเป็นทางการดังนี้:

ความเท่าเทียมกันของ PSPACE และ NPSPACE

เป็นที่น่าสนใจว่าการอนุญาตให้เครื่องจักรทัวริงเป็นแบบไม่กำหนดสภาวะ (Nondeterministic) ไม่ได้ช่วยเพิ่มพลังในการคำนวณในแง่ของพื้นที่หน่วยความจำ เนื่องจาก ทฤษฎีบทของซาวิทช์ (Savitch's theorem) ระบุว่า

มีค่าเท่ากับ

เพราะเครื่องจักรทัวริงแบบกำหนดสภาวะสามารถจำลองเครื่องจักรทัวริงแบบไม่กำหนดสภาวะได้โดยใช้พื้นที่เพิ่มขึ้นเพียงแค่การยกกำลังสอง ซึ่งพหุนามยกกำลังสองยังคงเป็นพหุนาม

นอกจากนี้ ส่วนเติมเต็ม (Complement) ของปัญหาใน PSPACE จะอยู่ใน PSPACE ด้วยเช่นกัน ซึ่งหมายความว่า

ความสัมพันธ์ระหว่างคลาสความซับซ้อน

ความสัมพันธ์ระหว่าง PSPACE และคลาสความซับซ้อนอื่นๆ เช่น NL, P, NP, PH, EXPTIME และ EXPSPACE มีดังนี้ (โดยที่ ⊂ หมายถึงเซตย่อยแท้ และ ⊆ หมายถึงเซตย่อยที่อาจเท่ากันได้):

• 

• 

จากความสัมพันธ์ข้างต้น เป็นที่สงสัยกันอย่างกว้างขวางว่าความสัมพันธ์ทั้งหมดเป็นเซตย่อยแท้ แต่ในปัจจุบันยังไม่มีการพิสูจน์ได้ทั้งหมด อย่างไรก็ตาม มีการพิสูจน์แล้วว่า NL ⊂ PSPACE และ PSPACE ⊂ EXPSPACE โดยใช้ทฤษฎีบทลำดับชั้นของพื้นที่ (Space Hierarchy Theorem)

คุณสมบัติการปิด (Closure Properties)

คลาส PSPACE มีคุณสมบัติการปิดภายใต้การดำเนินการ ยูเนียน (Union), ส่วนเติมเต็ม (Complementation) และ คลีนสตาร์ (Kleene star)

การระบุลักษณะอื่นๆ

PSPACE สามารถระบุลักษณะได้ในรูปแบบอื่นๆ ดังนี้:

• APTIME (AP): คือเซตของปัญหาที่ตัดสินได้โดยเครื่องจักรทัวริงแบบสลับ (Alternating Turing Machine) ในเวลาพหุนาม
• ตรรกศาสตร์อันดับสอง (Second-order logic): ในทางทฤษฎีความซับซ้อนเชิงพรรณนา PSPACE คือเซตของปัญหาที่แสดงออกได้ในตรรกศาสตร์อันดับสองที่มีการเพิ่มตัวดำเนินการ transitive closure
• ระบบการพิสูจน์แบบโต้ตอบ (Interactive Proof System): ผลลัพธ์สำคัญคือ PSPACE เท่ากับคลาส IP ซึ่งหมายถึงภาษาที่สามารถรับรู้ได้โดยระบบการพิสูจน์แบบโต้ตอบที่มีผู้พิสูจน์ (Prover) ผู้ทรงพลังและผู้ตรวจสอบ (Verifier) ที่ทำงานในเวลาพหุนามแบบสุ่ม
• ควอนตัม: PSPACE สามารถระบุลักษณะได้เป็นคลาสความซับซ้อนทางควอนตัม QIP