NP คือคลาสของภาษาที่มีตัวตรวจสอบเวลาพหุนาม
คลาส NP ซึ่งย่อมาจาก "เวลาพหุนามที่ไม่สามารถกำหนดได้" เป็นแนวคิดพื้นฐานในทฤษฎีความซับซ้อนในการคำนวณ ซึ่งเป็นสาขาย่อยของวิทยาการคอมพิวเตอร์เชิงทฤษฎี เพื่อทำความเข้าใจ NP ก่อนอื่นเราต้องเข้าใจแนวคิดของปัญหาการตัดสินใจ ซึ่งเป็นคำถามที่มีคำตอบใช่หรือไม่ใช่ ภาษาในบริบทนี้อ้างอิงถึงชุดของสตริงเหนือตัวอักษรบางตัว โดยแต่ละสตริงจะเข้ารหัสอินสแตนซ์ของปัญหาการตัดสินใจ
กล่าวกันว่าภาษา (L) อยู่ใน NP หากมีตัวตรวจสอบเวลาแบบพหุนามสำหรับ (L) ตัวตรวจสอบคืออัลกอริธึมที่กำหนดขึ้นเอง (V) ที่รับอินพุต 1 ตัว: อินสแตนซ์ (x) และใบรับรอง (y) ใบรับรอง (y) เรียกอีกอย่างว่า "พยาน" หรือ "หลักฐาน" ผู้ตรวจสอบ (V) ตรวจสอบว่าใบรับรอง (y) ยืนยันว่า (x) เป็นของภาษา (L) หรือไม่ อย่างเป็นทางการ ภาษา (L) อยู่ใน NP หากมีอัลกอริธึมเวลาพหุนาม (V) และพหุนาม (p(n)) ในลักษณะที่ว่าสำหรับทุกสตริง (x ใน L) จะมีสตริง (y) ที่มี ( |y|.leq p(|x|)) และ (V(x, y) = 1) ในทางกลับกัน สำหรับทุกสตริง (x ไม่ใช่ L) จะไม่มีสตริง (y) ที่ทำให้ (V(x, y) = XNUMX)
เพื่ออธิบายแนวคิดนี้ ให้พิจารณาปัญหาที่รู้จักกันดีของ "ความพึงพอใจแบบบูลีน" (SAT) ปัญหา SAT ถามว่ามีการมอบหมายค่าความจริงให้กับตัวแปรในสูตรบูลีนที่กำหนดหรือไม่ เพื่อให้สูตรประเมินค่าเป็นจริง ปัญหา SAT อยู่ใน NP เพราะด้วยสูตรบูลีน ( phi ) และการมอบหมาย ( alpha ) ของค่าความจริงให้กับตัวแปร เราสามารถตรวจสอบในเวลาพหุนามว่า ( alpha ) เป็นไปตาม ( phi ) หรือไม่ ในที่นี้ อินสแตนซ์ ( x ) คือสูตรบูลีน ( phi ) และใบรับรอง ( y ) คือการกำหนด ( alpha ) ตัวตรวจสอบ ( V ) ตรวจสอบว่า ( alpha ) ทำให้ ( phi ) เป็นจริงหรือไม่ ซึ่งสามารถทำได้ในเวลาพหุนามเทียบกับขนาดของ ( phi )
ตัวอย่างอีกตัวอย่างหนึ่งคือปัญหา "เส้นทางฮามิลโทเนียน" ปัญหานี้ถามว่ามีเส้นทางในกราฟที่กำหนดซึ่งเยี่ยมชมแต่ละจุดยอดเพียงครั้งเดียวหรือไม่ ปัญหาเส้นทางแฮมิลตันยังอยู่ใน NP เพราะเมื่อพิจารณาจากกราฟ ( G ) และลำดับจุดยอด ( P ) เราสามารถตรวจสอบได้ในเวลาพหุนามว่า ( P ) เป็นเส้นทางแฮมิลตันใน ( G ) ในกรณีนี้ ตัวอย่าง ( x ) คือกราฟ ( G ) และใบรับรอง ( y ) คือลำดับของจุดยอด ( P ) ตัวตรวจสอบ ( V ) ตรวจสอบว่า ( P ) สร้างเส้นทางแฮมิลตันหรือไม่ ซึ่งสามารถทำได้ในเวลาพหุนามเทียบกับขนาดของ ( G )
แนวคิดของการตรวจสอบเวลาพหุนามมีความสำคัญเนื่องจากเป็นแนวทางในการกำหนดลักษณะของปัญหาที่สามารถตรวจสอบได้อย่างมีประสิทธิภาพ แม้ว่าการหาคำตอบอาจเป็นไปไม่ได้ด้วยการคำนวณก็ตาม นำไปสู่คำถามที่มีชื่อเสียงว่า (P = NP) ซึ่งถามว่าปัญหาทุกปัญหาที่สามารถตรวจสอบคำตอบได้ในเวลาพหุนามนั้นสามารถแก้ได้ในเวลาพหุนามหรือไม่ คลาส (P) ประกอบด้วยปัญหาการตัดสินใจที่สามารถแก้ไขได้ในเวลาพหุนามโดยใช้เครื่องทัวริงแบบกำหนดได้ ถ้า (P = NP) แสดงว่าปัญหาทุกปัญหาที่มีตัวตรวจสอบเวลาพหุนามมีตัวแก้เวลาพหุนามด้วย คำถามนี้ยังคงเป็นหนึ่งในปัญหาเปิดที่สำคัญที่สุดในวิทยาการคอมพิวเตอร์
คุณสมบัติหลักอย่างหนึ่งของ NP คือปิดภายใต้การลดเวลาพหุนาม การลดเวลาพหุนามจากภาษา ( L_1 ) เป็นภาษา ( L_2 ) เป็นฟังก์ชันคำนวณเวลาพหุนาม ( f ) โดยที่ ( x ใน L_1 ) ก็ต่อเมื่อ ( f(x) ใน L_2 ) หากมีการลดเวลาพหุนามจาก ( L_1 ) เป็น ( L_2 ) และ ( L_2 ) อยู่ใน NP ดังนั้น ( L_1 ) ก็อยู่ใน NP เช่นกัน คุณสมบัตินี้เป็นเครื่องมือในการศึกษาความสมบูรณ์ของ NP ซึ่งระบุปัญหาที่ "ยากที่สุด" ใน NP ปัญหาจะสมบูรณ์ NP หากอยู่ใน NP และทุกปัญหาใน NP สามารถลดลงได้ในเวลาพหุนาม ปัญหา SAT เป็นปัญหาแรกที่พิสูจน์แล้วว่าสมบูรณ์ NP และทำหน้าที่เป็นพื้นฐานในการพิสูจน์ความสมบูรณ์ NP ของปัญหาอื่นๆ
เพื่ออธิบายแนวคิดเรื่องความสามารถในการตรวจสอบพหุนาม-เวลาเพิ่มเติม ให้พิจารณาปัญหา "ผลรวมเซตย่อย" ปัญหานี้ถามว่ามีเซตย่อยของชุดจำนวนเต็มที่กำหนดซึ่งรวมเข้ากับค่าเป้าหมายที่ระบุหรือไม่ ปัญหาผลรวมเซตย่อยอยู่ใน NP เนื่องจากเมื่อกำหนดชุดของจำนวนเต็ม ( S ) ค่าเป้าหมาย ( t ) และเซตย่อย ( S' ) ของ ( S ) เราสามารถตรวจสอบในเวลาพหุนามว่าผลรวมขององค์ประกอบใน ( S' ) เท่ากับ ( t ) ที่นี่ อินสแตนซ์ ( x ) คือคู่ ( (S, t) ) และใบรับรอง ( y ) คือเซตย่อย ( S' ) เครื่องตรวจสอบ ( V ) ตรวจสอบว่าผลรวมขององค์ประกอบใน ( S' ) เท่ากับ ( t ) ซึ่งสามารถทำได้ในเวลาพหุนามเทียบกับขนาดของ ( S )
ความสำคัญของการตรวจสอบเวลาพหุนามนั้นขยายออกไปไกลเกินกว่าการพิจารณาทางทฤษฎี ในทางปฏิบัติ หมายความว่าสำหรับปัญหาใน NP หากมีการเสนอวิธีแก้ปัญหา (ใบรับรอง) ก็สามารถตรวจสอบได้อย่างมีประสิทธิภาพ ซึ่งมีผลอย่างมากต่อโปรโตคอลการเข้ารหัส ปัญหาการเพิ่มประสิทธิภาพ และสาขาต่างๆ ที่การตรวจสอบความถูกต้องของวิธีแก้ปัญหาเป็นสิ่งสำคัญ
โดยสรุป คลาส NP ครอบคลุมปัญหาการตัดสินใจ ซึ่งโซลูชันที่นำเสนอสามารถตรวจสอบได้ในเวลาพหุนามโดยอัลกอริธึมที่กำหนด แนวคิดนี้เป็นรากฐานของทฤษฎีความซับซ้อนในการคำนวณ และมีผลกระทบอย่างลึกซึ้งต่อทั้งด้านทฤษฎีและปฏิบัติของวิทยาการคอมพิวเตอร์ การศึกษา NP ความสามารถในการตรวจสอบพหุนาม-เวลา และแนวคิดที่เกี่ยวข้อง เช่น ความสมบูรณ์ของ NP ยังคงเป็นงานวิจัยที่มีชีวิตชีวาและมีความสำคัญ
คำถามและคำตอบล่าสุดอื่น ๆ เกี่ยวกับ ความซับซ้อน:
- คลาส PSPACE ไม่เท่ากับคลาส EXPSPACE หรือไม่
- คลาสความซับซ้อน P เป็นส่วนย่อยของคลาส PSPACE หรือไม่
- เราสามารถพิสูจน์ได้ว่าคลาส Np และ P เหมือนกันหรือไม่โดยการค้นหาคำตอบพหุนามที่มีประสิทธิภาพสำหรับปัญหา NP ที่สมบูรณ์บน TM ที่กำหนดขึ้น
- คลาส NP สามารถเท่ากับคลาส EXPTIME ได้หรือไม่
- มีปัญหาใน PSPACE ที่ไม่มีอัลกอริทึม NP ที่รู้จักหรือไม่
- ปัญหา SAT สามารถเป็นปัญหาที่สมบูรณ์ของ NP ได้หรือไม่
- ปัญหาอาจอยู่ในคลาสความซับซ้อนของ NP ได้หรือไม่ หากมีเครื่องทัวริงที่ไม่สามารถกำหนดได้ซึ่งจะแก้ไขในเวลาพหุนาม
- P และ NP เป็นคลาสความซับซ้อนเดียวกันจริงหรือ
- ทุกบริบทเป็นภาษาฟรีในคลาสความซับซ้อน P หรือไม่
- มีความขัดแย้งระหว่างคำจำกัดความของ NP ในฐานะคลาสของปัญหาการตัดสินใจกับตัวตรวจสอบพหุนาม-เวลา และความจริงที่ว่าปัญหาในคลาส P ก็มีตัวตรวจสอบเวลาพหุนามด้วยหรือไม่
ดูคำถามและคำตอบเพิ่มเติมในความซับซ้อน