确定性时间复杂性类

可判定性只问计算最终能否完成，DTIME 进一步给每个输入长度一只统一的最坏情况时钟。确定性意味着每个配置只有一个后继，所以给定输入只有一条运行轨迹；时钟到期前没有第二条分支可供选择。

与非确定性时间类理路非确定性时间复杂性类Nondeterministic time class · NTIME由非确定性图灵机在给定时间界内判定的语言集合。相比，DTIME 的接受和拒绝都由这条唯一轨迹决定。两类使用同一输入长度与单分支步数，但非确定机器以“存在接受分支”为成员语义；这一区别不能解释为随机选择或免费并行。

线性时间的奇偶语言 ​

考虑

确定性机器从左到右扫描输入，只在有限控制中保存“目前为偶数还是奇数”，故在 $n+O(1)$ 步内判定它，得到 $\mathrm{PARITY}\in \mathrm{DTIME}(n)$。在逐符号访问模型中还需要 $\mathrm{\Omega }(n)$ 次读取：若某位置从未被查看，把该位翻转不会改变机器轨迹，却会改变正确答案。这一对上下界给出 $\mathrm{\Theta }(n)$，而不是只凭算法写下一个宽松的 $O(n^2)$。

精细时间界依赖模型 ​

多带图灵机可以把中间结果放在不同工作带上；单带机模拟它时通常产生额外开销。因此“属于 $\mathrm{DTIME}(n^2)$”必须连同机器模型阅读。例如把输入、各带内容及头标记依次写在一条带上，一次模拟步扫描 $O(n+t(n))$ 个编码格，找到各头位置并实施原机转移；连同初始化，直接构造耗时 $O(n+t(n)(n+t(n)))$。当 $t(n)\ge n$ 时，它才简化为 $O(t(n{)}^2)$。这个直接构造虽不总最优，却具体说明为什么线性时间可能失去、但多项式时间仍保留。讨论线性或近线性时间时不能省略模型。

定义与层级条件 ​

平均、期望与摊还运行时间都不进入 DTIME 的最坏确定性量词。时间可构造性也只在调用时间层级定理理路时间层级定理Time hierarchy theorem在可构造时间界下，给予更多渐近时间会严格扩大可判定语言类。等结果时加入；例如病态函数可以定义一个 DTIME 类，却未必允许对角化机器精确执行相应时钟。

若 $t(n)\in O(u(n))$，直接放宽时钟得到

运行 $O(t(n))$ 步的机器至多访问 $O(t(n))$ 个新工作格，所以还存在时间到空间的基本包含 $\mathrm{DTIME}(t(n))\subseteq \mathrm{DSPACE}(t(n))$。反向不成立于同一数量级：工作空间可以反复复用，停机计算的时间可能远大于空间。

P理路复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 是 $\bigcup _{k\ge 1}\mathrm{DTIME}(n^k)$，EXP理路复杂性类 EXPEXPTIME · EXP可由确定性图灵机在单指数时间内判定的语言类。 则把预算扩大到 $2^{n^{O(1)}}$。这些并集类对合理模型的多项式模拟较稳健；精细的 DTIME 类仍负责记录实际模拟开销。