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