NP-khó

NP-khó là một tập hợp các bài toán trong lý thuyết độ phức tạp tính toán "ít nhất là khó ngang bất kì bài toán nào trong NP". Một bài toán H là NP-khó khi và chỉ khi có một bài toán NP-đầy đủ L quy về H trong thời gian đa thức.

Từ định nghĩa trên, ta nhận thấy

• Bài toán H ít nhất là khó bằng L do ta có thể dùng H để giải L
• Do L là NP-đầy đủ, và do đó là khó nhất trong NP, nên bài toán H ít nhất là khó bằng NP, nhưng H không nhất thiết là trong NP
• Nếu P ≠ NP, thì các bài toán NP-khó không thể giải được trong thời gian đa thức, nhưng nếu P=NP thì vẫn chưa thể biết một bài toán NP-khó cụ thể có thể giải được trong thời gian đa thức hay không.

Ví dụ

Có rất nhiều bài toán NP-khó, chẳng hạn bài toán người bán hàng, cây Steiner nhỏ nhất, bài toán xếp ba lô, v.v...

Có những bài toán là NP-khó nhưng không phải NP-đầy đủ, chẳng hạn bài toán dừng. Bài toán này yêu cầu xác định xem với một chương trình và dữ liệu vào cho trước, liệu chương trình có chạy mãi mãi hay không.

Quy ước đặt tên trong NP

NP-khó

Ít nhất khó ngang bất kì bài toán nào trong NP. Một bài toán có thể là NP-khó nhưng không nằm trong NP.

NP-đầy đủ

NP-khó và nằm trong NP. Đây là những bài toán khó nhất trong NP.

Đọc thêm

• Michael R. Garey và David S. Johnson (1979). [1] Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.