Cái thường được xem như là một mô hình trừu tượng khoa học mô phỏng những nhiệm vụ tính toán thừa nhận một thuật toán hiệu quả?
Lớp độ phức tạp P thường được xem như là một mô hình trừu tượng toán học những nhiệm vụ tính toán thừa nhận một thuật toán hiệu quả. Giả thuyết này được gọi là luận án Cobham-Edmonds. Lớp độ phức tạp NP, mặt khác, chứa nhiều vấn đề mà mọi người muốn giải quyết một cách hiệu quả, nhưng mà không có thuật toán hiệu quả được biết đến, chẳng hạn như vấn đề thoả mãn Boolean, vấn đề đường dẫn Hamilton và vấn đề bao gồm đỉnh. Kể từ khi máy Turing xác định là máy Turing đặc biệt không xác định, nó có thể dễ dàng quan sát thấy rằng mỗi vấn đề trong P cũng là thành viên của lớp NP.