DTIME

Trong lý thuyết độ phức tạp tính toán, DTIME (hoặc TIME) đại diện cho thời gian tính toán của máy Turing đơn định. DTIME được dùng để định nghĩa các lớp độ phức tạp bao gồm các bài toán quyết định giải được trong một giới hạn thời gian nhất định. Nếu các dữ liệu vào có kích thước n giải được trong thời gian f(n) thì bài toán nằm trong lớp độ phức tạp DTIME(f(n)) (hoặc TIME(f(n))).

Các lớp độ phức tạp trong DTIME

Có nhiều lớp độ phức tạp tính toán quan trọng được định nghĩa theo DTIME. DTIME thỏa mãn định lý cấp bậc thời gian, nghĩa là, nói một cách đơn giản, với mọi giới hạn thời gian, luôn có những bài toán giải được trong giới hạn đó nhưng không giải được trong thời gian ít hơn.

Lớp độ phức tạp P bao gồm tất cả các bài toán giải được trong thời gian đa thức. Có thể định nghĩa P như sau:

${\displaystyle {\mbox{P}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}(n^{k})}$

Một lớp lớn hơn sử dụng thời gian đơn định là EXPTIME, chứa tất cả các bài toán giải được trong thời gian hàm mũ.

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).}$

Có thể định nghĩa các lớp độ phức tạp lớn hơn một cách tương tự. Theo định lý cấp bậc thời gian, ta biết ${\displaystyle {\mbox{P}}\subsetneq {\mbox{EXPTIME}}}$.

Mô hình tính toán

Việc thay đổi mô hình tính toán cụ thể không ảnh hưởng nhiều đến các lớp DTIME. Các kết quả trong nghiên cứu thường sử dụng mô hình máy Turing nhiều băng. Máy Turing nhiều băng không thể nhanh hơn căn bậc hai của thời gian trên máy một băng.(Papadimitriou (1994), Định lý 2.1).

Nhân với một hằng số không làm thay đổi khả năng của các lớp DTIME. Luôn có thể tăng tốc với tỉ lệ hằng số bằng cách tăng số trạng thái trong máy hữu hạn trạng thái. Theo Papadimitriou (1994), định lý 2.2, với mọi ngôn ngữ ${\displaystyle L\in DTIME(f(n))}$ và mọi ${\displaystyle \epsilon >0}$, ${\displaystyle L\in DTIME(f'(n))}$, trong đó ${\displaystyle f'(n)=\epsilon f(n)+n+2}$.

Ghi chú

• American Mathematical Society (2004). Rudich, Steven và Avi Wigderson (biên tập). Computational Complexity Theory. American Mathematical Society and Institute for Advanced Study. ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.