形式陈述

对时间界 $t(n)$$t(n)$，$\mathrm{NTIME}(t(n))$$\mathrm{NTIME}(t(n))$ 是由非确定性图灵机在每个长度 $n$$n$ 输入上、所有计算分支均不超过 $O(t(n))$$O(t(n))$ 步，并以“存在接受分支”判定的语言类。等价地，对适当的 $t$$t$，成员资格可由长度 $O(t(n))$$O(t(n))$ 的证书和确定性 $O(t(n))$$O(t(n))$ 时间验证关系刻画。$NP=\bigcup_{k\ge1}\mathrm{NTIME}(n^k)$$NP=\bigcup _{k\ge 1}\mathrm{NTIME}(n^k)$，而 $NEXP=\bigcup_k\mathrm{NTIME}(2^{n^k})$$NEXP=\bigcup _k\mathrm{NTIME}(2^{n^k})$。

直觉

非确定时间把组合搜索中的候选选择视为猜测，再只为成功候选计一条验证路径；它描述“短证据能否快速检查”，并不赋予现实机器免费指数并行。

例子与边界

SAT 属于 NP，因为赋值是多项式长度证书，代入公式可快速验证。若机器有一条很短接受分支、另有无限分支，标准时间有界 NTM 定义仍要求所有分支受时间界控制，通常通过时钟截断。确定性模拟枚举所有分支可导致指数开销，因此 $\mathrm{DTIME}(t)\subseteq\mathrm{NTIME}(t)$$\mathrm{DTIME}(t)\subseteq \mathrm{NTIME}(t)$，反向只知粗略指数模拟。NTIME 的“接受存在”与 coNTIME 的“拒绝存在”不是同一语义。

推论与应用

NTIME 统一定义 NP、NEXP 与非确定时间层级，支撑证书、归约和完全性理论，也让算法中的猜测—验证模式成为可比较的资源量。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。