เอ็นพี (ความซับซ้อน)

ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน
เอ็นพี เป็นเซตของปัญหาการตัดสินใจที่สามารถหาคำตอบได้ด้วยเครื่องจักรทัวริงเชิงไม่กำหนด (non-deterministic Turing machine) ภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
เอ็นพี เป็นเซตของปัญหาการตัดสินใจที่สามารถตรวจคำตอบได้ภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต ด้วย เครื่องจักรทัวริงเชิงกำหนด (deterministic Turing machine)
คำว่า "ตรวจคำตอบ" ในที่นี้มีความหมายค่อนข้างจะคลุมเครือ ซึ่งรายละเอียดในส่วนนี้จะถูกอธิบายในไม่ช้า
== บทนำ ==
เอ็นพี เป็นคลาสของปัญหาที่ใหญ่มาก ประกอบด้วยปัญหาสำคัญมากมาย (รวมทั้งปัญหาทั้งหมดที่อยู่ในพีด้วย) ปัญหาบางอย่างในเอ็นพีค่อนข้างเป็นนามธรรมที่ดูเหมือนกับว่าจะไม่มีประโยชน์อะไรเลยในชีวิตจริง แต่ปัญหาส่วนใหญ่ที่ถูกนำมาใช้อย่างมากในงานอุตสาหกรรมและการคำนวณต่างๆ ก็เป็นปัญหาในกลุ่มเอ็นพีเช่นกัน ตัวอย่างเช่น ปัญหาการออกแบบเครือข่ายเพื่อให้ราคาถูกที่สุด ปัญหาการหาเส้นทางเดินครบรอบที่ประหยัดที่สุด ปัญหาการแบ่งและจัดลำดับการทำงานสำหรับคอมพิวเตอร์ ฯลฯ
== นิยามของเอ็นพี (แบบเป็นทางการ) ==
นิยามแบบเป็นทางการของเอ็นพีมีสองแบบ
=== นิยามแบบแรก -- เครื่องจักรทัวริงเชิงไม่กำหนด ===
เราจะกล่าวว่าปัญหาการตัดสินใจ \pi อยู่ภายในเอ็นพี เมื่อ เราสามารถหาเครื่องจักรทัวริงเชิงไม่กำหนด M ที่มีคุณสมบัติดังต่อไปนี้
M ทำงานจบภายในจำนวนเสตปที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ใช่" จะมีอย่างน้อย 1 เส้นทางการคำนวณ (computation path) ของ M(x) ที่ให้คำตอบว่า "ใช่"
ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ไม่ใช่" ทุกเส้นทางการคำนวณของ M(x) จะให้คำตอบว่าไม่ใช่
ลองมาดูตัวอย่างกันสักสองสามตัวอย่าง
เริ่มจากปัญหาที่เข้าใจได้ง่าย พิจารณาปัญหา "จำนวน x เป็นจำนวนประกอบหรือไม่?" ปัญหานี้จะตอบว่า "ใช่" ถ้าจำนวนที่กำหนดให้เป็นจำนวนประกอบ สำหรับปัญหานี้เราสามารถออกแบบเครื่องจักรทัวริงเชิงไม่กำหนดให้ทำงานดังต่อไปนี้
M(x) 
เลือกจำนวน y ที่มีค่ามากกว่า 2 แต่น้อยกว่า x มา 1 จำนวน
ถ้า y หาร x ลงตัว ตอบว่า "ใช่"
ตอบว่า "ไม่ใช่"
พิจารณาการทำงานของเครื่องจักรทัวริงในสองกรณี กรณีแรก ถ้า x เป็นจำนวนประกอบ จะมีทางเป็นไปได้ว่าจำนวน y ที่ M เลือกจะหาร x ลงตัว กรณีที่สอง ถ้า x ไม่ใช่จำนวนประกอบ ไม่ว่า M จะเลือกจำนวนใดมาก็ตาม คำตอบที่ได้จะเป็น "ไม่ใช่" เสมอ จากการมีอยู่ของ M ดังกล่าว เราสามารถสรุปได้ว่าปัญหานี้อยู่ในเอ็นพี
ถัดมา พิจารณา ปัญหาความสอดคล้องแบบบูล เราสามารถออกแบบเครื่องจักรทัวริงเชิงไม่กำหนดดังต่อไปนี้ โดยเครื่องจักร M จะรับนิพจน์ \phi(x_1,x_2, \ldots, x_n)  มา แล้วตัดสินว่านิพจน์นี้สามารถแทนค่า x_1,x_2, \ldots, x_n เพื่อทำให้นิพจน์เป็นจริงได้หรือไม่
M(\phi) 
for i :=1 to n
เลือกค่า x_i จาก (true, false)
แทนค่าที่เลือกทั้งหมดลงใน \phi แล้วตอบว่า "ใช่" ถ้า \phi เป็นจริง ถ้าไม่งั้นแล้วให้ตอบ "ไม่ใช่"
=== นิยามแบบที่สอง -- การตรวจคำตอบ ===
เราจะกล่าวว่าปัญหาการตัดสินใจ \pi อยู่ภายในเอ็นพี เมื่อ เราสามารถหาเครื่องจักรทัวริงเชิงกำหนด V ที่มีคุณสมบัติดังต่อไปนี้ (V เป็นตัวแทนของ verifier)
V ทำงานจบภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ใช่" จะมีบทพิสูจน์ w ที่ทำให้ V(x,w) ตอบว่า "ใช่"
ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ไม่ใช่" ไม่ว่าบทพิสูจน์ w จะเป็นอะไรก็ตาม V(x,w) จะตอบว่า "ไม่ใช่"
บทพิสูจน์ w มีขนาดเป็นฟังก์ชันพหุนามกับขนาดของอินพุต
หมายเหตุ: w มีชื่อเรียกหลายแบบ  ที่นิยมเรียกกันก็คือ พยาน (witness) , บทพิสูจน์ (proof) , และ certificate
ลองมาดูตัวอย่างเดียวกันแต่ใช้นิยามของเอ็นพีแบบที่สองในการพิสูจน์ดูบ้าง เริ่มจากปัญหาจำนวนประกอบก่อน เราสามารถออกแบบ V ได้ดังนี้
V(x,w) 
ถ้า w หาร x ลงตัว ตอบว่า "ใช่"
ตอบว่า "ไม่ใช่"
สังเกตว่าถ้า x เป็นจำนวนประกอบ จะมีบทพิสูจน์ w (ซึ่งในที่นี้ บทพิสูจน์ก็คือจำนวนที่หารจำนวนประกอบ x ลงตัว) ที่ทำให้ V ตอบว่า "ใช่" แต่ในทางกลับกันหาก x เป็นจำนวนเฉพาะ จะไม่มีบทพิสูจน์ใดที่ทำให้ V ตอบว่า "ใช่"
ลองมาดูตัวอย่างของ ปัญหาความสอดคล้องแบบบูล อีกครั้ง เราสามารถออกแบบ V ได้โดย
V(\phi, w) 
ถ้า w ไม่อยู่ในรูปแบบของ w= w_1 w_2 \ldots w_n ตอบว่า "ไม่ใช่"
แทนค่า \phi(w_1, w_2, \ldots, w_n)  แล้วตอบว่า "ใช่" ถ้า \phi เป็นจริง ถ้าไม่งั้นแล้วให้ตอบ "ไม่ใช่"
จะเห็นว่าในปัญหานี้บทพิสูจน์ของเราก็คือค่าของตัวแปรที่ทำให้นิพจน์เป็นจริงนั่นเอง
=== การสมมูลกันของนิยาม ===
เนื้อหาในส่วนนี้จะกล่าวถึงแนวคิดของบทพิสูจน์ว่าทำไมนิยามทั้งสองแบบนี้จึงสมมูลกันได้ การพิสูจน์แยกออกเป็นสองส่วนในส่วนแรกต้องพิสูจน์ว่าหากเซ็ต A ถูกจัดว่าเป็นเอ็นพีตามนิยามแบบแรกแล้ว A จะต้องเป็นเอ็นพีตามนิยามแบบที่สองด้วย และในส่วนที่สองเราต้องพิสูจน์ในกรณีกลับกัน
นิยามแบบแรก \rightarrow นิยามแบบที่สอง
สมมติว่าปัญหา A มีเครื่องจักรทัวริงเชิงไม่กำหนด M ที่ใช้เวลาการคำนวณเป็นฟังก์ชันพหุนามกับขนาดของอินพุต เราสามารถสร้างเครื่องจักรทัวริงเชิงกำหนด V ที่ simulate M โดยพิจารณาบทพิสูจน์ที่จะตรวจสอบคือบิตสตริงที่บ่งบอกถึงทางเลือกของ M และ V จะตอบ "ใช่" หากท้ายสุดแล้วสตริงที่บ่งบอกทางเลือกทำให้  M ทำงานจบในสถานะที่ตอบ "ใช่" เราลองมาวิเคราะห์การทำงานของ V กันดู
หาก x เป็นตัวอย่างของปัญหาที่ตอบ "ใช่" บทพิสูจน์ที่เป็นทางเลือกที่ทำให้ A ตอบรับจะผ่านการตรวจสอบของ V
หาก x เป็นตัวอย่างของปัญหาที่ตอบ "ไม่ใช่" จะไม่มีบทพิสูจน์ใดที่ผ่านการตรวจสอบของ V ได้
มีรายละเอียดปลีกย่อยที่ต้องจัดการอีกหน่อยคือ M อาจจะมีจำนวนทางเลือกมากกว่าสองในการเลือกแต่ละครั้ง ทำให้ไม่สามารถใช้บิตสตริงในการกำหนดทางเลือกได้ กรณีนี้สามารถแก้ได้ง่ายโดยการแปลง M ไปเป็น M' โดยที่ทุกครั้งที่ M' ใช้สมบัติการเลือกของเครื่องจักรทัวริงเชิงไม่กำหนด ทางเลือกของ A' จะมีเพียงสองเท่านั้น
นิยามแบบที่สอง \rightarrow นิยามแบบแรก
สมมติว่าปัญหา A เป็นเอ็นพีตามนิยามแบบที่สอง นั่นก็คือมีเครื่องจักรทัวริงเชิงกำหนด V ที่ทำหน้าที่ในการตรวจสอบตามนิยาม เราสามารถสร้างเครื่องจักรทัวริงเชิงไม่กำหนด M ที่รับอินพุต x ที่สอดคล้องกับนิยามแบบแรกโดยการให้ M ใช้ความสามารถของเครื่องจักรทัวริงเชิงไม่กำหนดในการเลือกบทพิสูจน์ w สำหรับ V หลังจากนั้น M simulate การทำงานของ V(x,w) และ M ตอบรับเมื่อ V(x,w) ให้คำตอบว่า "ใช่" เราสามารถวิเคราะห์เป็นสองกรณีได้ในวิธีเดียวกันกับบทพิสูจน์ในส่วนแรก
== ทำไมบางปัญหาในเอ็นพีจึงยาก ==
เนื่องจากว่าปัญหาที่อยู่ในกลุ่มนี้หลายอย่างมีประโยชน์เป็นอย่างมากในการแก้ปัญหาในชีวิตจริง นักวิจัยหลายคนจึงพยายามที่จะหาขั้นตอนวิธีที่มีประสิทธิภาพ (ทำงานในเวลาที่เป็นพหุนามกับขนาดของอินพุต) ในการแก้ปัญหาเหล่านี้ แต่ว่า จนกระทั่งปัจจุบัน ปํญหาหลายอย่างยังไม่สามารถหาขั้นตอนวิธีที่มีประสิทธิภาพได้
กลุ่มของปัญหาที่สำคัญเป็นอย่างมากในกลุ่มของเอ็นพีก็คือ เอ็นพีบริบูรณ์ ซึ่งมักจะถูกเรียกว่าเป็นกลุ่มของปํญหาที่ยากที่สุดในเอ็นพี เนื่องมาจากว่า การแก้ปัญหาเอ็นพีบริบูรณ์ได้อย่างมีประสิทธิภาพ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มของเอ็นพีได้อย่างมีประสิทธิภาพด้วย ในปัจจุบัน หากปัญหาใดถูกจัดอยู่ในกลุ่ม เอ็นพีบริบูรณ์ นักวิจัยจะเลิกล้มความคิดที่จะหาคำตอบของปํญหานั้น (อย่างมีประสิทธิภาพ) ทันที  โดยมักเปลี่ยนเป้าหมายไปที่การหาขั้นตอนวิธีแบบประมาณแทน
เราจะมาดูตัวอย่างของปัญหาปัญหาหนึ่งที่มีความก้าวหน้าอย่างสม่ำเสมอในเชิงของการหาอัลกอริธึมที่มีประสิทธิภาพสำหรับปัญหานั้น ปัญหานี้ก็คือปัญหา "จำนวนเฉพาะ (PRIME) " ซึ่งปัญหานี้ก็คือ
กำหนดจำนวนจำนวนหนึ่งมาให้ในรูปแบบของเลขฐานสอง ให้ตัดสินว่าจำนวนนี้เป็นจำนวนเฉพาะหรือไม่
เราสามารถเห็นได้ชัดเจนว่าปัญหานี้อยู่ใน โค-เอ็นพี เนื่องจากว่าหากว่าจำนวนที่รับมาเป็นจำนวนประกอบ เราสามารถใช้ความสามารถของเครื่องจักรทัวริงเชิงไม่กำหนดในการเลือกหาตัวประกอบจำนวนนั้น และตรวจสอบได้อย่างรวดเร็ว
การพิสูจน์ว่าปัญหานี้อยู่ใน เอ็นพี สามารถทำได้โดยการให้เครื่องจักรทัวริงเชิงไม่กำหนดเลือกหา generator ของกรุ๊ป ที่ประกอบด้วยจำนวนตั้งแต่ 1 ถึง n และตรวจสอบได้ในเวลารวดเร็ว และเนื่องมาจากว่าในกรณีที่ n ไม่เป็นจำนวนเฉพาะ เราจะไม่สามารถหา generator ได้ ปัญหานี้จึงอยู่ในเอ็นพี
ถัดมา ปัญหานี้ถูกพิสูจน์ว่าอยู่ใน อาร์พี และ โค-อาร์พี และอัลกอริธึมที่นำมาใช้ในการตรวจสอบถูกนำไปเป็นตัวอย่างของขั้นตอนวิธีแบบสุ่มในชั้นเรียน วิชาขั้นตอนวิธี เนื่องมาจากความง่าย และยังทำให้เห็นถึงความสามารถของการสุ่มที่ช่วยทำให้แก้ปัญหาที่ยากได้ง่ายขึ้น
ในปี 2545 ปัญหานี้ถูกพิสูจน์ว่าอยู่ใน พี เป็นการปิดปัญหานี้ลงอย่างสมบูรณ์
จะเห็นว่าการจัดปัญหานี้เข้าไปใน โค-เอ็นพี ค่อนข้างจะง่ายและชัดเจน แต่หลังจากนั้นนักวิจัยต้องใช้ความพยายามอย่างมากในการจัดปัญหานี้เข้าไปใน เอ็นพี อาร์พี และ พี ตามลำดับ
== นิยามแบบอื่นๆของเอ็นพี ==
ลองมอง เอ็นพี ในรูปแบบของ ระบบการพิสูจน์เชิงโต้ตอบ (Interactive Proof System) ที่ประกอบด้วย คนพิสูจน์ (Prover) และคนตรวจสอบ (verifier) และมองว่าคนตรวจสอบต้องการที่จะตรวจสอบว่าตัวอย่างของปัญหาที่ให้มาเป็นตัวอย่างที่ตอบ "ใช่" ในนิยามแบบนี้ เอ็นพีก็คือระบบที่มีคนตรวจสอบที่มีคุณสมบัติดังต่อไปนี้
สำหรับตัวอย่างของปัญหาที่ตอบ "ใช่" คนพิสูจน์สามารถหาบทพิสูจน์ (proof, witness, or certificate) ที่คนตรวจสอบยอมรับได้
สำหรับตัวอย่างของปัญหาที่ตอบ "ไม่ใช่" ไม่ว่าคนพิสูจน์จะส่งบทพิสูจน์ใดก็ตามให้กับคนตรวจสอบ คนตรวจสอบสามารถหาจุดที่ผิดพลาดในบทพิสูจน์นั้นได้เสมอ
ลองนึกถึงความยากลำบากของคนตรวจสอบบทพิสูจน์ หากต้องอ่านบทพิสูจน์ทั้งหมดทุกครั้งคงเหนื่อยไม่น้อยเพราะบทพิสูจน์ในบางครั้งอาจจะยาวมากกว่า 100 หน้า แต่ก็จำเป็นที่จะต้องอ่านอย่างละเอียดเพราะว่าไม่ต้องการให้บทพิสูจน์ผิดๆผ่านการตรวจสอบไปได้ ในที่นี้ความคิดของ ระบบการพิสูจน์ที่สามารถตรวจสอบเชิงสุ่มได้ (Probabilistically Checkable Proof) จึงเกิดขึ้น ในระบบนี้คนตรวจสอบสามารถสุ่มตรวจสอบบทพิสูจน์เป็นบางจุดได้ และแน่นอนว่ามีความเป็นไปได้ว่า บทพิสูจน์ที่ผิดๆอาจจะผ่านตาไปได้เป็นบางครั้ง แต่จุดที่สำคัญอย่างหนึ่งคือบทพิสูจน์ที่ถูกต้องจะถูกยอมรับเสมอ
ผลงานที่ยิ่งใหญ่ที่สุดอย่างหนึ่งในวิทยาการคอมพิวเตอร์เชิงทฤษฎีก็คือ "นิยามแบบใหม่ของเอ็นพี" โดยใช้ระบบการพิสูจน์ที่สามารถตรวจสอบเชิงสุ่มได้ โดยที่นิยามแบบใหม่บอกไว้ว่า เอ็นพีก็คือระบบที่มีคนตรวจสอบที่มีคุณสมบัติดังนี้
สำหรับตัวอย่างของปัญหาที่ตอบ "ใช่" คนพิสูจน์จะหาบทพิสูจน์ที่คนตรวจสอบยอมรับได้เสมอ
สำหรับตัวอย่างของปัญหาที่ตอบ "ไม่ใช่" ไม่ว่าบทพิสูจน์ใดๆจะถูกส่งมา คนตรวจสอบสามารถหาจุดผิดพลาดได้ด้วยความน่าจะเป็น อย่างน้อย \frac{1}{2}
และ คนตรวจสอบใช้การสุ่มไม่เกิน O(\log n)  บิตและจำนวนครั้งในการอ่านบทพิสูจน์ไม่เกินค่าคงที่ค่าหนึ่ง
นิยามแบบนี้ของ เอ็นพี บอกเราว่าคนตรวจสอบสามารถสุ่มอ่านบทพิสูจน์เป็นจุดๆ (spot-check) ได้ ผลงานนี้มีประโยชน์มหาศาลในการนำไปพิสูจน์ความยากของปัญหาการประมาณ
== ตัวอย่าง ==
ปัญหาที่สำคัญที่อยู่ในเอ็นพีก็คือ
ปัญหาสมสัณฐานของกราฟ (Graph Isomorphism)
ปัญหาการเดินทางของพนักงานขาย (Traveling Salesman Problem)
ปัญหาความสอดคล้องแบบบูล (Boolean Satisfiability Problem)
== อ้างอิง ==
Complexity Zoo 
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp.979-983.
Sections 7.3-7.5 (The Class NP, NP-completeness, Additional NP-complete Problems) , pp.241-271.
อเอ็นพี (ความซับซ้อน)
อเอ็นพี (ความซับซ้อน)