Vấn đề nào trong C khó hơn X?
Điều này thúc đẩy khái niệm về một bài toán khó đối với một lớp độ phức tạp. Một bài toán X khó đối với một lớp bài toán C nếu mọi bài toán trong C có thể được rút gọn về X. Do đó, không có bài toán nào trong C khó hơn X, vì một thuật toán cho X cho phép chúng ta giải bất kỳ bài toán nào trong C. Tất nhiên, khái niệm về các bài toán khó phụ thuộc vào loại phép rút gọn được sử dụng. Đối với các lớp độ phức tạp lớn hơn P, phép rút gọn trong thời gian đa thức thường được sử dụng. Đặc biệt, tập hợp các bài toán khó cho NP là tập hợp các bài toán cứng NP.