非确定性图灵机

非确定性既不是随机选择，也不是物理上的免费并行，而是把一次计算定义成分支树：只要存在一串合法选择形成接受路径，输入就被接受。它最适合表达“猜测一个证书，再确定性验证”，因此存在量词是核心，而不是概率。确定性模拟必须系统地按层交错搜索全部有限分支，所以它最终会发现任意有限接受路径。这直接证明的是可识别性等价；对判定器，还需要所有分支停机，使有限分支计算树可被完整搜索。时间复杂度中，即使树深有界，树宽仍可指数增长。

判定 SAT 的 NTM 可猜测每个变量的真值，再在线性于公式大小的时间内检查公式；只要公式可满足，就有一条接受分支。若把每次分支误当作等概率随机选择，一个只有唯一满足赋值的公式成功概率可能是 $2^{-n}$，这与“存在一条接受分支”的语义完全不同。拒绝要求没有接受分支，而不是存在一条拒绝分支；NTM 不会扩展可计算函数的集合，但可能把已知确定性运行时间显著缩短。

单个分支永不停止会使朴素深度优先模拟陷入该路径，并错过另一条接受分支。若输入没有接受分支却有无限分支，广度交错模拟也不会停机，这不妨碍它成为识别器，却不能证明它是判定器。在每条分支都有统一多项式时间界的复杂度定义中，计算树深度才自然有界。

NTM 为 NP、NPSPACE 和证书验证提供统一模型，把组合搜索中的“猜测—验证”模式转化为精确复杂性定义。图灵机公理库图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。的非确定版本与确定版本在可识别性上等价，却导出 NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 这样的复杂度类；再把工作带限制在线性空间内，得到经典线性有界自动机公理库线性有界自动机Linear-bounded automaton · LBA工作带可访问区域被输入长度的常数倍限制的非确定性图灵机。，其与上下文有关语言的对应由CSL–LBA 等价定理公理库CSL–LBA 等价定理CSL-LBA equivalence · Kuroda theorem上下文有关语言恰为非确定性线性有界自动机接受的语言。给出。非确定性始终表示存在接受分支，不应改写成随机选择。