ปัญหาที่ยังแก้ไม่ตกในวิทยาการคอมพิวเตอร์

⁠ ⁠${\displaystyle {\mathsf {P{\overset {?}{=}}PSPACE}}}$

ยังมีปัญหาที่ยังแก้ไม่ตกอีกมากมายในสาขาวิทยาการคอมพิวเตอร์

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

ถ้าเรากำหนดให้เซตของปัญหาทั้งหมดที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงโดยใช้พื้นที่สำหรับฟังก์ชันบางอย่างของขนาดอินพุตเราสามารถกำหนดอย่างเป็นทางการได้ดังนี้^{[ 1 ]}${\displaystyle {\mathsf {SPACE}}(f(n))}$${\displaystyle O(f(n))}$${\displaystyle f}$${\displaystyle n}$${\displaystyle {\mathsf {PSPACE}}}$

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {SPACE}}(n^{k}).}$

ปรากฏว่าการอนุญาตให้เครื่องจักรทัวริงไม่เป็น^แบบกำหนดไม่ได้เพิ่มพลังพิเศษใดๆ เนื่องจากทฤษฎีบทของ Savitch [ ^{2 ]}เทียบเท่ากับเนื่องจากเครื่องจักรทัวริงแบบกำหนดสามารถจำลองเครื่องจักรทัวริงแบบไม่กำหนดได้ในขณะที่ใช้พื้นที่ประมาณกำลังสอง และการยกกำลังสองจะทำให้พหุนามกลายเป็นพหุนาม (ที่ใหญ่กว่า) ^{[ 3 ]} นอกจากนี้ส่วนเติมเต็มของปัญหาทั้งหมดในก็อยู่ใน ด้วยเช่นกันซึ่งหมายความว่า^{[ 4 ]}${\displaystyle {\mathsf {NPSPACE}}}$${\displaystyle {\mathsf {PSPACE}}}$${\displaystyle {\mathsf {PSPACE}}}$${\displaystyle {\mathsf {PSPACE}}}$${\displaystyle {\mathsf {coPSPACE}}={\mathsf {PSPACE}}}$

ความสัมพันธ์ต่อไปนี้เป็นที่ทราบกันดีระหว่าง PSPACE และคลาสความซับซ้อนNL , P , NP , PH , EXPTIMEและEXPSPACE (ในที่นี้เราใช้ NL เพื่อแสดงถึงการบรรจุอย่างเข้มงวด ซึ่งหมายถึงเซตย่อยที่แท้จริง ในขณะที่ NP รวมถึงความเป็นไปได้ที่ทั้งสองเซตจะเป็นเซตเดียวกัน): ${\displaystyle \subset }$${\displaystyle \subseteq }$

${\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subset PSPACE\subset EXPSPACE}}\\{\mathsf {P\subset EXPTIME}}\end{array}}}$

จากบรรทัดที่สาม สรุปได้ว่าทั้งในบรรทัดแรกและบรรทัดที่สอง อย่างน้อยหนึ่งในเซตการบรรจุจะต้องเป็นแบบเข้มงวด แต่ยังไม่ทราบว่าเป็นแบบใด มีการคาดการณ์กันอย่างกว้างขวางว่าทั้งหมดเป็นแบบเข้มงวด

เงื่อนไขการบรรจุในบรรทัดที่สามทั้งสองเงื่อนไขเป็นที่ทราบกันดีว่าเป็นเงื่อนไขที่เข้มงวด เงื่อนไขแรกได้มาจากการหาค่าเฉพาะโดยตรง ( ทฤษฎีบทลำดับชั้นของปริภูมิ , NL ⊂ NPSPACE) และข้อเท็จจริงที่ว่า PSPACE = NPSPACE ผ่านทฤษฎีบทของ Savitchเงื่อนไขที่สองได้มาจากทฤษฎีบทลำดับชั้นของปริภูมิโดยตรง

ปัญหาที่ยากที่สุดใน PSPACE คือปัญหา PSPACE-complete ดูตัวอย่างปัญหาที่คาดว่าอยู่ใน PSPACE แต่ไม่อยู่ใน NP ได้ที่ PSPACE-complete

ชั้นเรียน PSPACE ปิดให้บริการภายใต้การดำเนินการสหภาพการเสริมและดาวคลีน

ลักษณะเฉพาะอีกประการหนึ่งของ PSPACE คือชุดของปัญหาที่สามารถตัดสินได้ด้วยเครื่องจักรทัวริงแบบสลับในเวลาพหุนาม บางครั้งเรียกว่า APTIME หรือเรียกสั้น ๆ ว่า AP ^{[ 5 ]}

ลักษณะเชิงตรรกะของ PSPACE จาก ทฤษฎี ความซับซ้อนเชิงพรรณนาคือ PSPACE เป็นเซตของปัญหาที่สามารถแสดงได้ในตรรกะลำดับที่สองโดยการเพิ่มตัว ดำเนิน การปิดแบบส่งผ่าน (transitive closure operator) ไม่จำเป็นต้องมีตัวดำเนินการปิดแบบส่งผ่านที่สมบูรณ์ ตัวดำเนินการปิดแบบส่งผ่านแบบสลับที่ได้ (commutative transitive closure ) และรูปแบบที่อ่อนกว่านั้นก็เพียงพอแล้ว การเพิ่มตัวดำเนินการนี้เองที่ (อาจจะ) ทำให้ PSPACE แตกต่างจากPH

ผลลัพธ์สำคัญประการหนึ่งของทฤษฎีความซับซ้อนคือ PSPACE สามารถอธิบายได้ว่าเป็นภาษาทั้งหมดที่ระบบพิสูจน์เชิงโต้ตอบ เฉพาะระบบ หนึ่งสามารถรับรู้ได้ ซึ่งเป็นระบบที่กำหนดคลาสIPในระบบนี้ มีผู้พิสูจน์ที่มีอำนาจทุกอย่างพยายามโน้มน้าวผู้ตรวจสอบแบบสุ่มที่ใช้เวลาในการประมวลผลแบบพหุนามว่าสตริงนั้นอยู่ในภาษา ผู้พิสูจน์ควรจะสามารถโน้มน้าวผู้ตรวจสอบได้ด้วยความน่าจะเป็นสูงหากสตริงนั้นอยู่ในภาษา แต่ไม่ควรจะสามารถโน้มน้าวได้เว้นแต่ด้วยความน่าจะเป็นต่ำหากสตริงนั้นไม่อยู่ในภาษา

PSPACE สามารถระบุลักษณะเป็นคลาสความซับซ้อนควอนตัมQIPได้^{[ 6 ]}

PSPACE ยังเท่ากับ P _CTCซึ่งเป็นปัญหาที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์แบบคลาสสิกโดยใช้เส้นโค้งไทม์ไลค์แบบปิด [ ^{7 ] เช่น}เดียวกับ BQP _CTCซึ่งเป็นปัญหาที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ควอนตัมโดยใช้เส้นโค้งไทม์ไลค์แบบปิด^{[ 8 ]}

ภาษาBเรียกว่าPSPACE-completeหากอยู่ใน PSPACE และเป็นภาษา PSPACE-hard ซึ่งหมายความว่าสำหรับทุกA ∈ PSPACE, โดยที่หมายความว่ามีการลดแบบ many-one ในเวลาพหุนามจากAไปยังBปัญหา PSPACE-complete มีความสำคัญอย่างยิ่งต่อการศึกษาปัญหา PSPACE เนื่องจากเป็นปัญหาที่ยากที่สุดใน PSPACE การค้นหาวิธีแก้ปัญหาแบบง่ายสำหรับปัญหา PSPACE-complete จะหมายความว่าเรามีวิธีแก้ปัญหาแบบง่ายสำหรับปัญหาอื่นๆ ทั้งหมดใน PSPACE เนื่องจากปัญหา PSPACE ทั้งหมดสามารถลดให้เป็นปัญหา PSPACE-complete ได้^{[ 9 ]}${\displaystyle A\leq _{\text{P}}B}$${\displaystyle A\leq _{\text{P}}B}$

ตัวอย่างของปัญหา PSPACE-complete คือปัญหาสูตรบูลีนเชิงปริมาณ (โดยปกติจะย่อเป็นQBFหรือTQBFโดยที่Tหมายถึง "จริง") ^{[ 9 ]}

• Papadimitriou, Christos (1993). ความซับซ้อนของการคำนวณ (ฉบับพิมพ์ครั้งที่ 1). Addison Wesley. ISBN 0-201-53082-1.บทที่ 19: ปริภูมิพหุนาม หน้า 455–490
• Sipser, Michael (2006). บทนำสู่ทฤษฎีการคำนวณ (ฉบับที่ 2). Thomson Course Technology. ISBN 0-534-95097-3.บทที่ 8: ความซับซ้อนของพื้นที่
• Williams, Ryan (2025-02-25). "การจำลองเวลาด้วยปริภูมิรากที่สอง". arXiv : 2502.17779 [ cs.CC ].

• สวนสัตว์แห่งความซับซ้อน : PSPACE