มีปัญหาใน PSPACE ที่ไม่มีอัลกอริทึม NP ที่รู้จักหรือไม่
ในขอบเขตของทฤษฎีความซับซ้อนในการคำนวณ โดยเฉพาะอย่างยิ่งเมื่อตรวจสอบคลาสความซับซ้อนของอวกาศ ความสัมพันธ์ระหว่าง PSPACE และ NP ถือเป็นความสนใจอย่างมาก เพื่อตอบคำถามโดยตรง: ใช่ มีปัญหาใน PSPACE ซึ่งไม่มีอัลกอริทึม NP ที่รู้จัก การยืนยันนี้มีรากฐานมาจากคำจำกัดความและความสัมพันธ์ระหว่างคลาสความซับซ้อนเหล่านี้
PSPACE คือคลาสของปัญหาการตัดสินใจที่สามารถแก้ไขได้ด้วยเครื่องจักรทัวริงโดยใช้พื้นที่จำนวนพหุนาม กล่าวอีกนัยหนึ่ง ปัญหาอยู่ใน PSPACE หากมีอัลกอริธึมที่สามารถแก้ปัญหาได้โดยใช้จำนวนหน่วยความจำที่มีขนาดพหุนามในขนาดของอินพุต ชั้นเรียนนี้ครอบคลุมปัญหาที่หลากหลาย ซึ่งบางปัญหาค่อนข้างซับซ้อนและเกี่ยวข้องกับกระบวนการคำนวณที่ซับซ้อน
ในทางกลับกัน NP คือระดับของปัญหาการตัดสินใจ ซึ่งโซลูชันที่เสนอสามารถตรวจสอบได้ในเวลาพหุนามโดยเครื่องทัวริงที่กำหนด ซึ่งหมายความว่าถ้ามีคนเสนอวิธีแก้ปัญหาแบบผู้สมัครให้กับคุณสำหรับปัญหาใน NP คุณสามารถตรวจสอบความถูกต้องของวิธีแก้ปัญหานั้นได้อย่างรวดเร็ว โดยเฉพาะในเวลาพหุนามที่สัมพันธ์กับขนาดอินพุต
ความสัมพันธ์ระหว่างสองคลาสนี้ทำให้ NP เป็นส่วนย่อยของ PSPACE เนื่องจากปัญหาใดๆ ที่สามารถตรวจสอบได้ในเวลาพหุนามก็สามารถแก้ไขได้ในปริภูมิพหุนามเช่นกัน เพื่อทำความเข้าใจว่าเหตุใด ให้พิจารณาว่าตัวตรวจสอบเวลาพหุนามสามารถอ่านจำนวนบิตของอินพุตและวิธีแก้ปัญหาที่เสนอได้เพียงจำนวนพหุนามเท่านั้น ดังนั้นจึงสามารถจำลองได้ด้วยเครื่องพหุนามอวกาศซึ่งติดตามตำแหน่งที่อ่านและการดำเนินการที่ได้ดำเนินการไป
อย่างไรก็ตาม การสนทนานี้ไม่เป็นความจริง นั่นคือไม่ทราบว่า PSPACE เป็นส่วนย่อยของ NP หรือไม่ ในความเป็นจริง เชื่อกันอย่างกว้างขวางว่า PSPACE มีปัญหาที่ไม่อยู่ใน NP แม้ว่าจะไม่ได้รับการพิสูจน์อย่างเป็นทางการก็ตาม ความเชื่อนี้มีพื้นฐานอยู่บนการมีอยู่ของปัญหาใน PSPACE ที่ดูเหมือนจะต้องใช้เวลามากกว่าพหุนามในการแก้ปัญหา แม้ว่าปัญหาเหล่านี้จะสามารถแก้ไขได้ด้วยปริภูมิพหุนามก็ตาม
หนึ่งในตัวอย่างที่ยอมรับได้ของปัญหาใน PSPACE ที่ไม่รู้ว่าอยู่ใน NP คือปัญหา Quantified Boolean Formula (QBF) QBF เป็นลักษณะทั่วไปของปัญหาความพึงพอใจแบบบูลีน (SAT) ซึ่งเป็น NP-สมบูรณ์ ในขณะที่ SAT ถามว่ามีการมอบหมายค่าความจริงให้กับตัวแปรที่ทำให้สูตรบูลีนที่กำหนดเป็นจริงหรือไม่ QBF เกี่ยวข้องกับปริมาณที่ซ้อนกันเหนือตัวแปร เช่น "สำหรับ x ทั้งหมด จะมีอยู่เพื่อให้สูตรเป็นจริง" การมีอยู่ของปริมาณเหล่านี้ทำให้ QBF ซับซ้อนมากขึ้นอย่างมีนัยสำคัญ QBF เสร็จสมบูรณ์ใน PSPACE ซึ่งหมายความว่ายากพอๆ กับปัญหาใดๆ ใน PSPACE หากมีอัลกอริทึม NP สำหรับ QBF ก็จะบอกเป็นนัยว่า NP เท่ากับ PSPACE ซึ่งเป็นผลลัพธ์ที่แปลกใหม่และถือว่าไม่น่าเป็นไปได้อย่างกว้างขวาง
อีกตัวอย่างหนึ่งคือปัญหาในการตัดสินผู้ชนะในเกมทั่วไป เช่น หมากรุกหรือหมากแบบทั่วไปที่เล่นบนกระดาน N x N ปัญหาเหล่านี้เกี่ยวข้องกับการเคลื่อนไหวและการกำหนดค่าจำนวนทวีคูณที่อาจเกิดขึ้น แต่สามารถตัดสินใจได้โดยใช้ปริภูมิพหุนามโดยการสำรวจสถานะของเกมที่เป็นไปได้ทั้งหมดอย่างเป็นระบบ ปัญหาเหล่านี้ยังสมบูรณ์ใน PSPACE อีกด้วย ซึ่งบ่งบอกถึงการมีอยู่ของปัญหาใน PSPACE ที่ไม่ได้อยู่ใน NP เพิ่มเติม
หากต้องการเจาะลึกว่าทำไมปัญหาบางอย่างใน PSPACE จึงเชื่อว่าอยู่นอก NP ให้พิจารณาธรรมชาติของการคำนวณแบบมีขอบเขตอวกาศและแบบมีขอบเขตเวลา พื้นที่พหุนามอนุญาตให้มีขั้นตอนการคำนวณเป็นจำนวนเอ็กซ์โพเนนเชียล ตราบใดที่พื้นที่ที่ใช้ยังคงมีขอบเขตพหุนาม สิ่งนี้แตกต่างอย่างสิ้นเชิงกับ NP ซึ่งเวลามีขอบเขตพหุนาม เวลาเอ็กซ์โปเนนเชียลที่อนุญาตโดยปริภูมิพหุนามสามารถใช้เพื่อแก้ปัญหาที่เกี่ยวข้องกับการค้นหาอย่างละเอียดในพื้นที่ขนาดใหญ่เอ็กซ์โพเนนเชียล เช่นที่พบใน QBF และเกมทั่วไป
นอกจากนี้ยังมีโครงสร้างทางทฤษฎีที่ซับซ้อนซึ่งสนับสนุนความแตกต่างระหว่าง PSPACE และ NP ต่อไป ตัวอย่างเช่น แนวคิดของการสลับที่นำเสนอโดย Chandra, Kozen และ Stockmeyer ทำให้เกิดความไม่แน่นอนและนำไปสู่คลาส AP (เวลาพหุนามสลับกัน) มีการแสดงให้เห็นว่า AP เท่ากับ PSPACE ดังนั้นจึงให้มุมมองที่แตกต่างเกี่ยวกับพลังของการคำนวณปริภูมิพหุนาม การสลับเกี่ยวข้องกับลำดับของปริมาณที่มีอยู่และปริมาณสากล ซึ่งสะท้อนโครงสร้างของ QBF และแสดงให้เห็นถึงความซับซ้อนที่มีอยู่ในปัญหา PSPACE
นอกจากนี้ยังเป็นที่น่าสังเกตว่าการแยกชั้นเรียนที่ซับซ้อนเป็นคำถามเปิดพื้นฐานในวิทยาการคอมพิวเตอร์เชิงทฤษฎี ปัญหา P กับ NP ที่มีชื่อเสียงเป็นกรณีพิเศษของการสอบถามในวงกว้างนี้ ในทำนองเดียวกัน คำถามที่ว่า NP เท่ากับ PSPACE หรือไม่ยังคงไม่ได้รับการแก้ไข อย่างไรก็ตาม ฉันทามติในสาขานี้ ซึ่งอิงจากการศึกษาอย่างกว้างขวางและลักษณะของปัญหาที่ทราบก็คือ PSPACE น่าจะมีปัญหาที่ไม่ได้อยู่ใน NP
การมีอยู่ของปัญหาใน PSPACE ซึ่งไม่มีอัลกอริธึม NP ที่รู้จักได้รับการสนับสนุนโดยคำจำกัดความและความสัมพันธ์ระหว่างคลาสความซับซ้อนเหล่านี้ เช่นเดียวกับตัวอย่างที่เป็นรูปธรรม เช่น QBF และปัญหาเกมทั่วไป ตัวอย่างเหล่านี้เน้นย้ำถึงกระบวนการคำนวณแบบเอกซ์โปเนนเชียลที่ซับซ้อนและเป็นไปได้ ซึ่งสามารถจัดการได้ภายในปริภูมิพหุนาม แต่ไม่น่าจะจำกัดอยู่เพียงเวลาพหุนาม ดังนั้น จึงทำให้กระบวนการเหล่านั้นอยู่นอกขอบเขตของ NP
คำถามและคำตอบล่าสุดอื่น ๆ เกี่ยวกับ ความซับซ้อน:
- คลาส PSPACE ไม่เท่ากับคลาส EXPSPACE หรือไม่
- คลาสความซับซ้อน P เป็นส่วนย่อยของคลาส PSPACE หรือไม่
- เราสามารถพิสูจน์ได้ว่าคลาส Np และ P เหมือนกันหรือไม่โดยการค้นหาคำตอบพหุนามที่มีประสิทธิภาพสำหรับปัญหา NP ที่สมบูรณ์บน TM ที่กำหนดขึ้น
- คลาส NP สามารถเท่ากับคลาส EXPTIME ได้หรือไม่
- ปัญหา SAT สามารถเป็นปัญหาที่สมบูรณ์ของ NP ได้หรือไม่
- ปัญหาอาจอยู่ในคลาสความซับซ้อนของ NP ได้หรือไม่ หากมีเครื่องทัวริงที่ไม่สามารถกำหนดได้ซึ่งจะแก้ไขในเวลาพหุนาม
- NP คือคลาสของภาษาที่มีตัวตรวจสอบเวลาพหุนาม
- P และ NP เป็นคลาสความซับซ้อนเดียวกันจริงหรือ
- ทุกบริบทเป็นภาษาฟรีในคลาสความซับซ้อน P หรือไม่
- มีความขัดแย้งระหว่างคำจำกัดความของ NP ในฐานะคลาสของปัญหาการตัดสินใจกับตัวตรวจสอบพหุนาม-เวลา และความจริงที่ว่าปัญหาในคลาส P ก็มีตัวตรวจสอบเวลาพหุนามด้วยหรือไม่
ดูคำถามและคำตอบเพิ่มเติมในความซับซ้อน