Bốn lớp phức tạp quan trọng khác là gì?
Các lớp độ phức tạp quan trọng khác bao gồm BPP, ZPP và RP, được xác định bằng máy Turing xác suất; AC và NC, được xác định bằng mạch Boolean; và BQP và QMA, được xác định bằng máy Turing lượng tử. #P là một lớp độ phức tạp quan trọng của các bài toán đếm (không phải bài toán quyết định). Các lớp như IP và AM được xác định bằng các hệ thống bằng chứng tương tác. ALL là lớp của tất cả các bài toán quyết định.