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

แผนภาพออยเลอร์แสดงความสัมพันธ์ของพี, เอ็นพี เอ็นพีบริบูรณ์ และเอ็นพีแบบยาก สำหรับทั้งสองกรณีที่พีเท่ากับเอ็นพี และพีไม่เท่ากับเอ็นพี

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

นิยาม

เราจะเรียกปัญหาการตัดสินใจ C ว่าเป็น เอ็นพีบริบูรณ์ เมื่อ

1. C เป็นปัญหาเอ็นพี
2. C เป็นปัญหาเอ็นพีแบบยาก (นั่นก็คือทุกปัญหาในเอ็นพีสามารถลดรูปเป็น C ได้)

วิธีการต่อกรกับเอ็นพีบริบูรณ์

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

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