เอ็นพีบริบูรณ์

ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ () เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ  กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C

 นิยาม 
เราจะเรียกปัญหาการตัดสินใจ C ว่าเป็น เอ็นพีบริบูรณ์ เมื่อ
 C เป็นปัญหาเอ็นพี
 C เป็นปัญหาเอ็นพีแบบยาก (นั่นก็คือทุกปัญหาในเอ็นพีสามารถลดรูปเป็น C ได้)

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

 ใช้การประมาณ เพื่อหาคำตอบที่พิสูจน์ได้ว่าไม่แย่เกินไปนัก 
 ใช้ขั้นตอนวิธีที่มีประสิทธิภาพสำหรับบางรูปแบบการกระจายตัวของอินพุต 
 จงใจตอบเฉพาะกรณีพิเศษ
 ใช้ฮิวริสติก ซึ่งจะทำให้ขั้นตอนวิธีทำงานได้ดีในหลาย ๆ กรณี แต่ไม่สามารถพิสูจน์อะไรได้เลย ในบางทีอาจจะได้คำตอบที่แย่เกินกว่าจะรับได้

หมวดหมู่:ทฤษฎีความซับซ้อนในการคำนวณ
หมวดหมู่:การหาค่าเหมาะที่สุดทางคณิตศาสตร์