นิยาม ของ เอ็นพีบริบูรณ์

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

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

ใกล้เคียง