Định lý nào chịu trách nhiệm cho việc xác định các câu hỏi về yêu cầu thời gian và không gian?
Đối với các lớp học phức tạp được xác định theo cách này, nó là mong muốn để chứng minh rằng thư giãn các yêu cầu về (nói) thời gian tính toán thực sự xác định một tập hợp lớn hơn của vấn đề. Đặc biệt, mặc dù DTIME(n) được chứa trong DTIME(n2), nó sẽ là thú vị để biết nếu sự bao gồm là nghiêm ngặt. Đối với các yêu cầu về thời gian và không gian, câu trả lời cho những câu hỏi như vậy được đưa ra bởi các định lý phân cấp thời gian và không gian tương ứng. Chúng được gọi là định lý phân cấp vì chúng tạo ra một hệ thống phân cấp thích hợp trên các lớp được xác định bằng cách hạn chế các nguồn lực tương ứng. Do đó, có những cặp lớp học phức tạp như vậy mà một trong những được bao gồm đúng trong khác. Sau khi suy luận bao gồm tập hợp thích hợp như vậy, chúng ta có thể tiến hành để làm cho báo cáo định lượng về bao nhiêu thêm thời gian hoặc không gian là cần thiết để tăng số lượng các vấn đề có thể được giải quyết.
Định lý phân cấp thời gian và không gian