✨Định lý cấp bậc thời gian

Trong lý thuyết độ phức tạp tính toán, các định lý cấp bậc thời gian là các mệnh đề quan trọng về tính toán trong thời gian giới hạn trên máy Turing. Nói một cách đơn giản, các định lý này cho thấy với nhiều thời gian hơn, máy Turing có thể giải được nhiều bài toán hơn. Ví dụ, có bài toán có thể giải trong thời gian n² nhưng không thể giải trong thời gian n.

Định lý cấp bậc thời gian cho máy Turing đơn định nhiều băng được chứng minh bởi Richard Stearns và Juris Hartmanis năm 1965. Một năm sau, chứng minh được cải tiến sau khi F.C. Hennie và Richard Stearns nâng cao được hiệu quả của máy Turing vạn năng. Định lý cấp bậc thời gian cho máy Turing đơn định khẳng định rằng với mọi hàm tính được trong giới hạn thời gian f(n), :$\backslash operatorname\{DTIME\}\backslash left(o\backslash left(\backslash frac\{f(n)\}\{\backslash log\; f(n)\}\backslash right)\backslash right)\; \backslash subsetneq\; \backslash operatorname\{DTIME\}(f(n))$

Định lý cấp bậc thời gian cho máy Turing không đơn định được chứng minh đầu tiên bởi Stephen Cook năm 1972. Nó được cải tiến thành dạng hiện nay bởi một chứng minh phức tạp của Joel Seiferas, Michael Fischer, and Albert Meyer năm 1978. Cuối cùng năm 1983, Stanislav Žác đã chứng minh được cùng kết quả đó với một chứng minh đơn giản được sử dụng trong giảng dạy hiện nay. Định lý cấp bậc thời gian cho máy Turing không đơn định khẳng định rằng nếu g(n) là một hàm tính được trong giới hạn thời gian, và f(n+1) = o(g(n)), thì :$\backslash operatorname\{NTIME\}(f(n))\; \backslash subsetneq\; \backslash operatorname\{NTIME\}(g(n))$.

Các định lý tương tự cho bộ nhớ là các định lý cấp bậc bộ nhớ. Hiện vẫn chưa có định lý tương tự cho các lớp độ phức tạp xác suất với giới hạn thời gian trừ phi các lớp đó có trợ giúp.