Loại giải pháp nào là một trong những đối tượng nghiên cứu trung tâm trong lý thuyết độ phức tạp tính toán?
Bài toán quyết định là một trong những đối tượng nghiên cứu trung tâm trong lý thuyết độ phức tạp tính toán. Bài toán quyết định là một loại bài toán tính toán đặc biệt có câu trả lời là có hoặc không, hoặc luân phiên là 1 hoặc 0. Bài toán quyết định có thể được xem như một ngôn ngữ chính thức, trong đó các thành viên của ngôn ngữ là các trường hợp có đầu ra là có và các thành viên không phải là các trường hợp có đầu ra là không. Mục tiêu là quyết định, với sự trợ giúp của thuật toán, liệu một chuỗi đầu vào nhất định có phải là thành viên của ngôn ngữ chính thức đang được xem xét hay không. Nếu thuật toán quyết định vấn đề này trả về câu trả lời có, thuật toán được cho là chấp nhận chuỗi đầu vào, nếu không nó được cho là từ chối đầu vào.