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

ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา **เอ็นพี** (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 เพื่อทำให้นิพจน์เป็นจริงได้หรือไม่

   *<math>M(\phi) </math>*
     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 ได้โดย

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

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

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

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

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

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

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

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

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

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

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

นิยามแบบนี้ของ **เอ็นพี** บอกเราว่าคนตรวจสอบสามารถสุ่มอ่านบทพิสูจน์เป็นจุดๆ (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.

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