Những vấn đề nào trên lý thuyết không thể giải quyết được, nhưng trong thực tế lại mất quá nhiều thời gian để có thể trở nên hữu ích?
Vấn đề có thể được giải quyết trong lý thuyết (ví dụ, cho lớn nhưng thời gian hữu hạn), nhưng mà trong thực tế mất quá nhiều thời gian cho các giải pháp của họ là hữu ích, được gọi là vấn đề khó khăn. Trong lý thuyết phức tạp, vấn đề thiếu giải pháp đa thức thời gian được coi là khó khăn cho nhiều hơn các yếu tố đầu vào nhỏ nhất. Trong thực tế, luận án Cobham-Edmonds nói rằng chỉ có những vấn đề có thể được giải quyết trong thời gian đa thức có thể được tính toán một cách khả thi trên một số thiết bị tính toán. Vấn đề được biết đến là khó khăn theo nghĩa này bao gồm những người đang EXPTIME-cứng. Nếu NP không phải là giống như P, sau đó các vấn đề NP-hoàn thành cũng là khó khăn theo nghĩa này. Để xem lý do tại sao thuật toán thời gian theo cấp số nhân có thể không sử dụng được trong thực tế, hãy xem xét một chương trình mà làm cho 2n hoạt động trước khi dừng lại. Đối với n nhỏ, nói 100, và giả sử vì lợi ích của ví dụ rằng máy tính không 1012 hoạt động mỗi giây, chương trình sẽ chạy trong khoảng 4 × 1010 năm, đó là cùng một thứ tự độ lớn như tuổi của vũ trụ. Ngay cả với một máy tính nhanh hơn nhiều, chương trình sẽ chỉ hữu ích cho các trường hợp rất nhỏ và theo nghĩa đó khả năng giải quyết của một vấn đề là hơi độc lập với tiến bộ công nghệ. Tuy nhiên, một thuật toán thời gian đa thức không phải lúc nào cũng thực tế. Nếu thời gian chạy của nó là, nói, n15, nó là không hợp lý để xem xét nó hiệu quả và nó vẫn là vô dụng ngoại trừ trên các trường hợp nhỏ.