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

ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (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 เก็บถาวร 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.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Sections 7.3-7.5 (The Class NP, NP-completeness, Additional NP-complete Problems) , pp.241-271.