Đị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.^[1] 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.^[2] Đị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),

${\displaystyle \operatorname {DTIME} \left(o\left({\frac {f(n)}{\log f(n)}}\right)\right)\subsetneq \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.^[3] 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.^[4] 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.^[5] Đị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ì

${\displaystyle \operatorname {NTIME} (f(n))\subsetneq \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.^[6]

Ghi chú

1. Hartmanis, J.; Stearns, R. E. (ngày 1 tháng 5 năm 1965). “On the computational complexity of algorithms”. Transactions of the American Mathematical Society. American Mathematical Society. 117: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. MR 0170805. Đã định rõ hơn một tham số trong |first1= và |first= (trợ giúp)
2. Hennie, F. C.; Stearns, R. E. (1966). “Two-Tape Simulation of Multitape Turing Machines”. J. ACM. New York, NY, USA: ACM. 13 (4): 533–546. doi:10.1145/321356.321362. ISSN 0004-5411.
3. Cook, Stephen A. (1972). “A hierarchy for nondeterministic time complexity”. Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. tr. 187–192. doi:10.1145/800152.804913.
4. Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (1978). “Separating Nondeterministic Time Complexity Classes”. J. ACM. New York, NY, USA: ACM. 25 (1): 146–167. doi:10.1145/322047.322061. ISSN 0004-5411.
5. Stanislav, Žác (1983). “A Turing machine time hierarchy”. Theoretical Computer Science. Elsevier Science B.V. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4.
6. Fortnow, L.; Santhanam, R. (2004). “Hierarchy Theorems for Probabilistic Polynomial Time”: 316. doi:10.1109/FOCS.2004.33.

Tham khảo

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Trang 310–313 ở phần 9.1: Hierarchy theorems.
• Christos Papadimitriou (1993). Computational Complexity (ấn bản thứ 1). Addison Wesley. ISBN 0-201-53082-1. Phần 7.2: The Hierarchy Theorem, pp. 143–146.