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