DTIME

在计算复杂度理论内，DTIME（或者TIME）是一个图灵机的计算资源或者计算时间的计量方式。它代表一个"普通"有实体的电脑解决特定计算问题，使用特定算法，所要花费的时间。这个计算资源是最被广泛研究的计算资源，因为它与真实世界所重视的资源（要花费多少时间才能计算出一个问题）息息相关。

DTIME这个资源常被使用来定义复杂度类，亦即，可以在特定时间内解决的决定性问题其集合。如果一个问题其输入的大小为n，并且可要求f(n)的计算时间来解决，那我们说这问题在DTIME(f(n))（or TIME(f(n))）里面。这里没有限制必须使用多少存储器空间（参见计算资源），但是有可能会限制一些其他的计算资源（像是可否使用交替图灵机）。

DTIME内的复杂度类

许多重要的复杂度类都使用DTIME来定义，这些类别包含需要花费特定时间才能解决的问题，来作为分类。任何适当复杂度函数（proper complexity function）都可以用来定义复杂度类，但是只有特定的类别较有被研究的价值。概括说来，我们希望复杂度类对计算方式的变化来讲足够稳定，另外对副函数的合成来讲会是封闭（close）的。

DTIME满足时间谱系理论，这代表在渐进分析内较大的时间，所产生的时间复杂度类严格大于（大于且不等于）其他时间复杂度类。

有名的复杂度类P代表所有可以在多项式内的DTIME解决的问题。我们可以正式定义为：

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

P是包含了线性问题${\displaystyle {\mbox{DTIME}}\left(n\right)}$的最小坚固（robust）复杂度类（AMS 2004, Lecture 2.2, pg. 20）。另外，P也是我们认为"可以实际运算"的最大复杂度类（其他的复杂度类时间成长太快，一般认为计算是不实际的）。

一个大上很多的，使用DTIME的复杂度类是EXPTIME，包含了代表所有可以在指数时间内以图灵机解决的问题。正式定义为：

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

我们可以用类似方法定义更大的复杂度类。因为时间谱系理论，这些复杂度类会组成严格的谱系（不会有哪个在上方者与下方相等）；换句话说，我们已知${\displaystyle {\mbox{P}}\subsetneq {\mbox{EXPTIME}}}$，并且依此类推。

机器模型

实际操作以定义DTIME的机器，可以在不影响DTIME定义的前提之下，换成其他的某些机器。最后作结论时，常常会使用多带图灵机，特别是在定义某些很小的复杂度类时。更准确的说，一个多带图灵机不可能提供超过一般图灵机平方时间以上的计算能力（Papadimitriou 1994, Thrm. 2.1）。

对时间进行常量倍数的加速并不影响DTIME内复杂度类的能力；因为常量倍数的加速永远可以用增加图灵机内状态的方式达成。在Papadimitriou（1994, Thrm. 2.2）内的陈述，对任何语言L，

令L ${\displaystyle \in }$ DTIME(f(n))。对任何${\displaystyle \epsilon }$ > 0, L ${\displaystyle \in }$ DTIME(f'(n))，则f'(n) = ${\displaystyle \epsilon }$ f(n) + n + 2.

推广

使用一般图灵机以外的机器，我们会得到许多DTIME之外的推广与限制。举例来说，如果我们使用非确定型图灵机，我们会得到名为NTIME的计算资源。对于DTIME的能力与其他计算资源的关系，我们仍所知甚少。

参考资料

• American Mathematical Society. Rudich, Steven and Avi Wigderson (ed.) , 编. Computational Complexity Theory. American Mathematical Society and Institute for Advanced Study. 2004. ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. Computational Complexity. Reading, Massachusetts: Addison-Wesley. 1994. ISBN 0-201-53082-1.