非确定性时间复杂性类

非确定时间把“存在一串成功选择”放进计算语义。每个分支仍是一段普通的、按步计费的局部计算；区别只在于成员输入只需有一条分支接受，而非成员输入必须让所有分支失败。它不为现实机器提供指数数量的免费处理器，也不是给分支随机分配概率。

与确定性时间类理路确定性时间复杂性类Deterministic time class · DTIME由确定性图灵机在给定时间界内判定的语言集合。相比，确定机器是每个配置最多一个后继的特例，因此相同预算下确定性计算自动也是非确定性计算。反向模拟通常要遍历整棵分支树，时间可能指数增长。

合数的猜测—验证 ​

把正整数用二进制编码，定义

若输入长度为 $n$，机器猜测两个至多 $n$ 位的整数 $a,b$，再用逐位乘法和比较验证条件，耗时为 $n$ 的多项式。对 $N=91$，猜到 $(7,13)$ 的分支接受；对 $N=97$，每一对候选都会因乘积或范围不符而拒绝。这个例子同时表明证书按二进制长度收费，不能把一次任意精度乘法暗算成常数步骤。

为什么所有分支都要有时钟 ​

设机器先分成两支：第一支立即接受，第二支永远向右移动。即使成员输入上存在很短的接受分支，第二支仍使机器不属于任何有限 NTIME 界。标准构造会给所有分支装上同一时钟；到期未接受就拒绝。

穷举模拟的代价 ​

取固定常数 $b\ge 2$ 作为机器分支度的上界（即使实际只有一个后继，也可放大到这个上界）。若树深为 $O(t(n))$，计算树最多有 $b^{O(t(n))}=2^{O(t(n))}$ 个节点。逐层确定性遍历因此给出粗略指数时间模拟，却没有给出 $\mathrm{NTIME}(t)\subseteq \mathrm{DTIME}(t^{O(1)})$。在多项式尺度上，后者正触及 P 与 NP 的开放问题。

每台确定机器都可视为从不真正分支的非确定机器，所以

把所有多项式预算取并得到NP理路复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。：

类似地，NEXP 使用 $2^{n^{O(1)}}$ 的非确定时间预算。若把问题从“是否有接受分支”改为“有多少条接受分支”，则进入#P理路计数复杂性类 #PSharp-P · #P可高效验证的见证计数类；由前缀计数构造均匀生成器，并给出近似计数到近均匀采样的完整误差预算。一类计数复杂度；存在性与计数不是同一输出任务。