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

จากวิกิพีเดีย สารานุกรมเสรี

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

[แก้] นิยาม

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

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

[แก้] วิธีการสู้กับเอ็นพีบริบูรณ์ -- ยอมตอบผิดเป็นบางครั้ง

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

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