Điều gì không thể giải quyết vấn đề ba lô NP-hoàn chỉnh trên một loạt các kích cỡ trong thời gian ít hơn bậc hai?
Trong thực tế, khả năng khả kiến có ý nghĩa gì thì vẫn còn đang được tranh luận. Nói rằng một bài toán không nằm trong P không có nghĩa là tất cả các trường hợp lớn của bài toán đều khó hoặc thậm chí hầu hết trong số chúng là như vậy. Ví dụ, bài toán quyết định trong số học Presburger đã được chứng minh là không nằm trong P, nhưng các thuật toán đã được viết ra để giải quyết vấn đề trong thời gian hợp lý trong hầu hết các trường hợp. Tương tự, các thuật toán có thể giải quyết bài toán ba lô NP-đầy đủ trong một loạt các kích cỡ trong thời gian ít hơn bậc hai và các trình giải SAT thường xuyên xử lý các trường hợp lớn của bài toán thoả mãn Boolean NP-đầy đủ.