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

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