Khác biệt giữa bản sửa đổi của “NP-khó”
Nội dung được xóa Nội dung được thêm vào
+interlink |
Không có tóm lược sửa đổi |
||
Dòng 1:
'''NP-khó''' là một tập hợp các bài toán trong [[Độ_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". Một bài toán H là NP-khó khi và chỉ khi có một bài toán NP-đầy đủ quy về H trong thời gian đa thức.
==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...
| |||