พื้นที่ความซับซ้อนแบบไม่กำหนดสภาวะ (NSPACE)

ในทฤษฎีความซับซ้อนในการคำนวณ NSPACE (Non-deterministic Space) คือทรัพยากรการคำนวณที่ใช้อธิบายปริมาณหน่วยความจำหรือพื้นที่ที่เครื่องทัวริงแบบไม่กำหนดสภาวะ (Non-deterministic Turing Machine) ต้องการในการประมวลผลปัญหาหนึ่งๆ โดย NSPACE เป็นคู่ขนานในรูปแบบไม่กำหนดสภาวะของ DSPACE ซึ่งใช้กับเครื่องทัวริงแบบกำหนดสภาวะ (Deterministic Turing Machine)

คลาสความซับซ้อนที่นิยามโดย NSPACE

ค่าการวัด NSPACE ถูกนำมาใช้เพื่อกำหนดคลาสความซับซ้อนของปัญหาที่สามารถหาคำตอบได้ด้วยเครื่องทัวริงแบบไม่กำหนดสภาวะ โดยคลาสความซับซ้อน NSPACE(f(n)) คือเซตของปัญหาการตัดสินใจ (Decision Problems) ที่สามารถแก้ไขได้โดยเครื่องทัวริงแบบไม่กำหนดสภาวะ M โดยใช้พื้นที่ในระดับ O(f(n)) เมื่อ n คือความยาวของข้อมูลนำเข้า

คลาสความซับซ้อนที่สำคัญหลายคลาสถูกนิยามผ่าน NSPACE ดังนี้:

• REG: DSPACE(O(1)) = NSPACE(O(1)) ซึ่งเป็นคลาสของภาษาปกติ (Regular Languages) โดยในกรณีของพื้นที่คงที่ การไม่กำหนดสภาวะไม่ได้ช่วยเพิ่มประสิทธิภาพในการคำนวณ
• NL: NSPACE(O(log n))
• CSL: NSPACE(O(n)) ซึ่งเป็นคลาสของภาษาสัมผัสบริบท (Context-Sensitive Languages)
• PSPACE: NPSPACE = ⋃_k∈ℕ NSPACE(n^k)
• EXPSPACE: NEXPSPACE = ⋃_k∈ℕ NSPACE(2^nk)

นอกจากนี้ ทฤษฎีบทของอิมเมอร์แมน-เซเลปเชนยี (Immerman–Szelepcsényi theorem) ระบุว่า NSPACE(s(n)) มีสมบัติปิดภายใต้คอมพลีเมนต์ (Closed under complement) สำหรับทุกฟังก์ชัน s(n) ≥ log n

ความสัมพันธ์กับคลาสความซับซ้อนอื่นๆ

ความสัมพันธ์กับ DSPACE

NSPACE มีความสัมพันธ์โดยตรงกับ DSPACE ซึ่งเป็นคลาสของพื้นที่หน่วยความจำบนเครื่องทัวริงแบบกำหนดสภาวะ ตามทฤษฎีบทของซาวิตช์ (Savitch's theorem) ความสัมพันธ์นี้สามารถเขียนได้ดังนี้:

โดยระบุว่า DSPACE[s(n)] ⊆ NSPACE[s(n)] ⊆ DSPACE[(s(n))²] ซึ่งหมายความว่าปัญหาใดๆ ที่แก้ได้ด้วยพื้นที่ s(n) แบบไม่กำหนดสภาวะ สามารถแก้ได้ด้วยพื้นที่ s(n) ยกกำลังสองแบบกำหนดสภาวะ

ความสัมพันธ์กับเวลา (Time Complexity)

NSPACE สามารถใช้เพื่อจำกัดความซับซ้อนทางเวลาแบบกำหนดสภาวะของปัญหาได้ โดยมีทฤษฎีระบุว่า หากภาษา L ถูกตัดสินในพื้นที่ S(n) (โดยที่ S(n) ≥ log n) ด้วยเครื่องทัวริงแบบไม่กำหนดสภาวะ จะมีค่าคงที่ C ที่ทำให้ L ถูกตัดสินได้ในเวลา O(C^S(n)) ด้วยเครื่องทัวริงแบบกำหนดสภาวะ

ข้อจำกัดในการใช้งาน

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