ดูต้นฉบับสำหรับ เอ็นพี (ความซับซ้อน)


{{ลิงก์ไปภาษาอื่น}}
ใน[[ทฤษฎีความซับซ้อนในการคำนวณ]] กลุ่มปัญหา '''เอ็นพี''' (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน

* '''เอ็นพี''' เป็น[[เซต]]ของปัญหาการตัดสินใจที่สามารถ'''หา'''คำตอบได้ด้วย[[เครื่องจักรทัวริงเชิงไม่กำหนด]] ([[:en:non-deterministic Turing machine|non-deterministic Turing machine]]) ภายในเวลาที่เป็นฟังก์ชัน[[พหุนาม]]กับขนาดของอินพุต 
* '''เอ็นพี''' เป็นเซตของปัญหาการตัดสินใจที่สามารถ'''ตรวจ'''คำตอบได้ภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต ด้วย [[เครื่องจักรทัวริงเชิงกำหนด]] ([[:en:deterministic Turing machine|deterministic Turing machine]])

คำว่า "ตรวจคำตอบ" ในที่นี้มีความหมายค่อนข้างจะคลุมเครือ ซึ่งรายละเอียดในส่วนนี้จะถูกอธิบายในไม่ช้า

== บทนำ ==
'''เอ็นพี''' เป็นคลาสของปัญหาที่ใหญ่มาก ประกอบด้วยปัญหาสำคัญมากมาย (รวมทั้งปัญหาทั้งหมดที่อยู่ในพีด้วย) ปัญหาบางอย่างในเอ็นพีค่อนข้างเป็นนามธรรมที่ดูเหมือนกับว่าจะไม่มีประโยชน์อะไรเลยในชีวิตจริง แต่ปัญหาส่วนใหญ่ที่ถูกนำมาใช้อย่างมากในงานอุตสาหกรรมและการคำนวณต่างๆ ก็เป็นปัญหาในกลุ่มเอ็นพีเช่นกัน ตัวอย่างเช่น ปัญหาการออกแบบเครือข่ายเพื่อให้ราคาถูกที่สุด ปัญหาการหาเส้นทางเดินครบรอบที่ประหยัดที่สุด ปัญหาการแบ่งและจัดลำดับการทำงานสำหรับคอมพิวเตอร์ ฯลฯ

== นิยามของเอ็นพี (แบบเป็นทางการ) ==
นิยามแบบเป็นทางการของเอ็นพีมีสองแบบ 

=== นิยามแบบแรก -- เครื่องจักรทัวริงเชิงไม่กำหนด ===

เราจะกล่าวว่าปัญหาการตัดสินใจ <math>\pi</math> อยู่ภายในเอ็นพี เมื่อ เราสามารถหา[[เครื่องจักรทัวริงเชิงไม่กำหนด]] 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 จะรับนิพจน์ <math>\phi(x_1,x_2, \ldots, x_n) </math> มา แล้วตัดสินว่านิพจน์นี้สามารถแทนค่า <math>x_1,x_2, \ldots, x_n</math> เพื่อทำให้นิพจน์เป็นจริงได้หรือไม่

   ''<math>M(\phi) </math>''
     for i :=1 to n 
        เลือกค่า <math>x_i</math> จาก (true, false) 
     แทนค่าที่เลือกทั้งหมดลงใน <math>\phi</math> แล้วตอบว่า "ใช่" ถ้า <math>\phi</math> เป็นจริง ถ้าไม่งั้นแล้วให้ตอบ "ไม่ใช่"

=== นิยามแบบที่สอง -- การตรวจคำตอบ ===

เราจะกล่าวว่าปัญหาการตัดสินใจ <math>\pi</math> อยู่ภายในเอ็นพี เมื่อ เราสามารถหา[[เครื่องจักรทัวริงเชิงกำหนด]] 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 ได้โดย

   ''<math>V(\phi, w) </math>''
     ถ้า w ไม่อยู่ในรูปแบบของ <math>w= w_1 w_2 \ldots w_n</math> ตอบว่า "ไม่ใช่" 
     แทนค่า <math>\phi(w_1, w_2, \ldots, w_n) </math> แล้วตอบว่า "ใช่" ถ้า <math>\phi</math> เป็นจริง ถ้าไม่งั้นแล้วให้ตอบ "ไม่ใช่"

จะเห็นว่าในปัญหานี้บทพิสูจน์ของเราก็คือค่าของตัวแปรที่ทำให้นิพจน์เป็นจริงนั่นเอง 

=== การสมมูลกันของนิยาม ===

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

'''นิยามแบบแรก <math>\rightarrow</math> นิยามแบบที่สอง'''

สมมติว่าปัญหา A มีเครื่องจักรทัวริงเชิงไม่กำหนด M ที่ใช้เวลาการคำนวณเป็นฟังก์ชันพหุนามกับขนาดของอินพุต เราสามารถสร้างเครื่องจักรทัวริงเชิงกำหนด V ที่ simulate M โดยพิจารณาบทพิสูจน์ที่จะตรวจสอบคือบิตสตริงที่บ่งบอกถึงทางเลือกของ M และ V จะตอบ "ใช่" หากท้ายสุดแล้วสตริงที่บ่งบอกทางเลือกทำให้  M ทำงานจบในสถานะที่ตอบ "ใช่" เราลองมาวิเคราะห์การทำงานของ V กันดู  
* หาก x เป็นตัวอย่างของปัญหาที่ตอบ "ใช่" บทพิสูจน์ที่เป็นทางเลือกที่ทำให้ A ตอบรับจะผ่านการตรวจสอบของ V 
* หาก x เป็นตัวอย่างของปัญหาที่ตอบ "ไม่ใช่" จะไม่มีบทพิสูจน์ใดที่ผ่านการตรวจสอบของ V ได้  

มีรายละเอียดปลีกย่อยที่ต้องจัดการอีกหน่อยคือ M อาจจะมีจำนวนทางเลือกมากกว่าสองในการเลือกแต่ละครั้ง ทำให้ไม่สามารถใช้บิตสตริงในการกำหนดทางเลือกได้ กรณีนี้สามารถแก้ได้ง่ายโดยการแปลง M ไปเป็น <math>M'</math> โดยที่ทุกครั้งที่ <math>M'</math> ใช้สมบัติการเลือกของเครื่องจักรทัวริงเชิงไม่กำหนด ทางเลือกของ <math>A'</math> จะมีเพียงสองเท่านั้น

'''นิยามแบบที่สอง <math>\rightarrow</math> นิยามแบบแรก'''

สมมติว่าปัญหา 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) จึงเกิดขึ้น ในระบบนี้คนตรวจสอบสามารถสุ่มตรวจสอบบทพิสูจน์เป็นบางจุดได้ และแน่นอนว่ามีความเป็นไปได้ว่า บทพิสูจน์ที่ผิดๆอาจจะผ่านตาไปได้เป็นบางครั้ง แต่จุดที่สำคัญอย่างหนึ่งคือบทพิสูจน์ที่ถูกต้องจะถูกยอมรับเสมอ

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

* สำหรับตัวอย่างของปัญหาที่ตอบ "ใช่" คนพิสูจน์จะหาบทพิสูจน์ที่คนตรวจสอบยอมรับได้เสมอ 
* สำหรับตัวอย่างของปัญหาที่ตอบ "ไม่ใช่" ไม่ว่าบทพิสูจน์ใดๆจะถูกส่งมา คนตรวจสอบสามารถหาจุดผิดพลาดได้ด้วยความน่าจะเป็น อย่างน้อย <math>\frac{1}{2}</math>

และ '''คนตรวจสอบใช้การสุ่มไม่เกิน <math>O(\log n) </math> บิตและจำนวนครั้งในการอ่านบทพิสูจน์ไม่เกินค่าคงที่ค่าหนึ่ง'''

นิยามแบบนี้ของ '''เอ็นพี''' บอกเราว่าคนตรวจสอบสามารถสุ่มอ่านบทพิสูจน์เป็นจุดๆ (spot-check) ได้ ผลงานนี้มีประโยชน์มหาศาลในการนำไปพิสูจน์ความยากของปัญหาการ[[ขั้นตอนวิธีแบบประมาณ|ประมาณ]]

== ตัวอย่าง ==
ปัญหาที่สำคัญที่อยู่ใน'''เอ็นพี'''ก็คือ 
* [[ปัญหาสมสัณฐานของกราฟ]] (Graph Isomorphism) 
* [[ปัญหาการเดินทางของพนักงานขาย]] (Traveling Salesman Problem)
* [[ปัญหาความสอดคล้องแบบบูล]] (Boolean Satisfiability Problem)

== อ้างอิง ==
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo#np Complexity Zoo] {{Webarchive|url=https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#np |date=2006-11-28 }} 
* [[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. 
* {{Cite book| author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | ID = ISBN 0-534-94728-X}} Sections 7.3-7.5 (The Class NP, NP-completeness, Additional NP-complete Problems) , pp.241-271.

[[หมวดหมู่:ทฤษฎีการคำนวณ|อเอ็นพี (ความซับซ้อน)]]
[[หมวดหมู่:ทฤษฎีความซับซ้อนในการคำนวณ|อเอ็นพี (ความซับซ้อน)]]