Một thuật toán có thể thể hiện các hành vi khác nhau trong nhiều lần chạy ngay cả khi sử dụng cùng một đầu vào được gọi là? Với câu hỏi trước, hãy viết một ngữ cảnh có chứa câu trả lời. Nó có thể là 1 - 20 câu. Nội dung
Lớp phức tạp P thường được coi là một sự trừu tượng toán học mô hình hóa những nhiệm vụ tính toán đó cho phép một thuật toán hiệu quả. Giả thuyết này được gọi là luận án Cobham-Edmonds. Ngược lại, lớp phức tạp NP 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 không có thuật toán hiệu quả nào được biết đến, chẳng hạn như vấn đề thỏa mãn Boolean, vấn đề đường Hamiltonian và vấn đề bao phủ đỉnh. Vì các máy Turing quyết định là các máy Turing không quyết định đặc biệt, 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.