概率 Turing 机

阐述

是非确定性 Turing 机的一种，其中每个非确定性的步骤具有两个可能的等概率分叉。因此该机器中一个分支的概率是

\operatorname{Pr}[b]=2^{-k}

定义 $M$ 接受 $w$ 的概率为

\operatorname{Pr}[M \text { accepts } w]=\sum \operatorname{Pr}[b]

称 $M$ 以误差 $\varepsilon$ 判定语言 $A$ ，如果

$w \in A \text { implies } \operatorname{Pr}[M \text { accepts } w] \geq 1-\epsilon$
$w \notin A \text { implies } \operatorname{Pr}[M \text { rejects } w] \geq 1-\epsilon$

这种误差可以被放大引理进一步缩小。设 $0<\varepsilon<1/2$ ，对于任何多项式 $p(n)$ ，如果存在一个误差为 $\varepsilon$ 的概率多项式 Turing 机 $M_1$ ，那么也存在一个误差为 $2^{-p(n)}$ 的 $M_2$ 。

能在概率 Turing 机上以多项式时间解决的问题称为 BPP 复杂度类。