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.