'''NP-khó''' là một tập hợp các bài toán trong [[Độ_phức_tạp_thuật_toánĐộ phức tạp thuật toán|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 (độ phức tạp)|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
Dòng 19:
== Đọc thêm ==
*{{citechú bookthích sách|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [http://www.amazon.com/dp/0716710455] [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}}
