非确定性图灵机

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

判定 SAT 的 NTM 可猜测每个变量的真值，再在公式编码长度的多项式时间内检查赋值。纸带机需要扫描、匹配变量编码并取回赋值，不能直接把随机访问模型中的逐门常数成本搬过来。只要公式可满足，就有一条接受分支。若误把分支当作等概率随机选择，一个含 $n$ 个变量且只有唯一满足赋值的公式，成功概率可能只有 $2^{-n}$，这与“存在一条接受分支”完全不同。

拒绝要求没有接受分支，而不是存在一条拒绝分支。NTM 不会扩展可计算函数的集合，但它给出的已知时间上界可能小于直接确定性搜索的上界；二者是否存在多项式与超多项式的差距，是另一个复杂性问题。

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

对一个固定输入，有限分支性加上所有分支停机，实际上保证整棵树有限：若它无限，König 引理会给出一条无限路径。因此广度优先模拟最终或找到接受节点，或耗尽全部节点后拒绝。这里得到的最大深度可以依赖输入，且尚无多项式上界；它足以证明可判定性等价，却不能证明 P 与 NP 相等。

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