07 概率图灵机

许多算法中会用到随机性，这类算法称为随机算法。一个随机算法可以看作是一系列确定性算法的分布。引入随机性一般有两种目的：第一种目的是，提供一个简单的解决方案使得我们能以期望意义下更高效地完成计算，例如在快速排序中我们不通过分析数据选取一个尽可能接近中位数的pivot，而是快速地选一个随机的pivot；第二种目的是，牺牲百分之百输出正确答案这一特性，而是设计一个高效得多的算法，该算法以较大概率输出正确答案。无论哪种目的，引入随机性都能提升算法的运行效率。

概率图灵机模型

确定性图灵机模型和非确定性图灵机模型都不足以刻画随机算法，所以我们引入概率图灵机(Probabilistic Turing Machine)。可以这样直观理解概率图灵机：如果说非确定性图灵机是一棵二叉树，那么概率图灵机就是这棵二叉树上随机的一条从根节点到叶节点的路径。严格来说，一个概率图灵机有两个迁移函数$\delta_0,\delta_1$；任何时候概率图灵机都会以$1/2$的概率选择某个迁移函数做状态转移；在某个固定的输入$x$下，概率图灵机的输出$\mathbb{P}(x)$是一个随机变量。

称概率图灵机$\mathbb{P}$在输入$x$后计算得到了$y$，如果$\Pr[\mathbb{P}(x)=y]>1/2$；否则称概率图灵机计算失败。由此，$\mathbb{P}$能判定问题$L$当且仅当$\forall x,\Pr[\mathbb{P}(x)=L(x)]>1/2$。这是一个相当自然的定义，也应当是唯一能被接受的定义方式。

Santos定理指出，概率图灵机可计算的函数就是一切确定性图灵机可计算的函数。这个定理告诉我们，引入概率图灵机并不会扩展“可计算”意义下模型的计算能力。

概率图灵机定义的复杂性类

注意到，我们对概率图灵机计算成功的要求仅仅是输出概率$>1/2$。这会引发下面这样一个结论：概率图灵机能以期望时间常数判定任何可判定的问题。这是因为，我们总是可以构造以下的概率图灵机：对一个可判定的问题，存在一台确定性图灵机$\mathbb{M}$判定之；令概率图灵机一步步模拟$\mathbb{M}$的计算，如果某步后$\mathbb{M}$停机输出$1$，我们令概率图灵机输出$1$；如果某步后$\mathbb{M}$停机输出$0$，我们输出$0$；否则，我们以$1/2$的概率继续模拟，以另外$1/2$的概率“以$1/2$的概率”输出结果。这会使得我们总能以期望常数的时间，以某个大于零的概率输出正确，并用剩下的概率以一半的概率猜对，也即输出正确的概率总是大于$1/2$。

基于以上分析，直接不加修饰地利用概率图灵机定义复杂性类是没有意义地。为了做出有意义的复杂性类的定义，有两种补救手段：一种是不以期望时间步数作为时间复杂度，而是以最坏情况的时间步数作为时间复杂度；一种是增加常数$\varepsilon$，要求$>1/2+\varepsilon$才算概率图灵机计算成功。我们分别讨论这两种情况。

概率多项式类(PP)

首先考虑以最坏情况的时间步数作为时间复杂度定义的复杂性类划分方式。对于概率图灵机$\mathbb{P}$，如果时间函数$T$满足$\forall x$，$\mathbb{P}(x)$计算成功的所有可能计算步数都不超过$T(|x|)$，就称$T$是$\mathbb{P}$的时间函数。如果$\mathbb{P}(x)$能在$cT(n)$内判定$L$，就称$L\in \text{PTIME}(T(n))$。

定义$\text{PP}=\bigcup\limits_{c>0}\text{PTIME}(n^c)$，称为概率多项式类(Probabilistic Polynomial time complexity class)，它包含所有概率图灵机在多项式时间内（最坏情况）可判定的问题。

根据最坏情况时间这一定义，自然有$\overline{\text{PP}}=\text{PP}$，也即$\text{PP}$在补运算下封闭。

根据定义可知，$\text{PP}\subseteq \text{PSPACE}$，因为所有概率多项式可判定的问题都可以在多项式空间用确定性图灵机模拟所有可能情况。

下面我们证明，$\text{NP}\subseteq \text{PP}$。对于一个能被非确定性图灵机在多项式时间判定的问题$L$，我们用概率图灵机依照概率模拟非确定性图灵机，模拟到某一时刻如果非确定性图灵机输出$1$，则概率图灵机也输出$1$；否则某一时刻非确定性图灵机输出$0$，此时概率图灵机以$1/2$的概率输出$0$或$1$。分析以上过程，如果非确定性图灵机确实存在一个输出$1$的终止状态，那么这一状态一定会以大于零的概率被模拟到，如果没被模拟到概率图灵机会以$1/2$的概率输出正确。综上，概率图灵机总是以$>1/2$的概率输出正确。

由此我们得到了$\text{PP}$类的上下界：$\text{NP}\subseteq \text{PP}\subseteq \text{PSPACE}$（或$\overline{\text{NP}}\subseteq \text{PP}\subseteq \text{PSPACE}$，因为$\text{PP}$在补运算下封闭）。

通过定义可以发现，$\text{PP}$类问题关心的是具有某个性质的对象是否占多数。所以它本质是一些计数问题，我们可以从计数的角度用确定性图灵机给出$\text{PP}$类的等价刻画：$L\in\text{PP}$当且仅当存在$\mathbb{M}$使得$\Pr\limits_{r}[\mathbb{M}(x,r)=L(x)]>1/2$，其中$r$是关于输入长度多项式长的随机串。换言之，我们可以用确定性图灵机模拟概率图灵机的每种可能性，然后统计其结果，这样就把用概率图灵机定义的复杂性类转化为了用确定性图灵机定义的复杂性类。

既然一个复杂性类是可以用确定性图灵机定义的，那么我们就可以用Karp归约定义其中的完全问题。$\text{PP}$类中的完全问题是什么？答案还是和SAT有管。人们证明了以下两个问题是$\text{PP}$-complete的：①基于SAT集合定义$\natural$SAT，$\lang \varphi,i\rang \in \natural$SAT当且仅当$\varphi$存在$>i$个可满足的赋值；②基于SAT集合定义MajSAT（Majority SAT），$\varphi \in$ SAT当且仅当$\varphi$的所有赋值中超过半数的赋值是可满足的。Gill证明了这两个问题都是$\text{PP}$-complete的，并且是等价的（可以相互归约）。

最后值得一提的是，对于大多数复杂性类都满足其中的问题关于交和并封闭。比如对于$\text{P}$（$\text{PSPACE}$），$L_1,L_2\in \text{P}\implies L_1\cap L_2 \in P$，$L_1\cup L_2\in P$，这根据定义是显然的。然而由于涉及概率，这对于$\text{PP}$不是显然的。然而人们证明了，关于交和并封闭的性质对$\text{PP}$也是成立的。

有界误差概率多项式类(BPP)

下面我们考虑第二种补救方法，也即用$>1/2+\varepsilon$来定义计算成功，而把最坏时间改为期望时间。而令人惊奇的是，我们可以证明（略），如果我们考虑的是多项式时间，那么用期望时间定义和用最坏时间定义是等价的。更进一步，如果我们考虑的是多项式时间，$\varepsilon$的取值并不重要。所以，关于$\text{BPP}$类，无论我们使用“最坏时间+$\varepsilon=1/6$”定义还是用“期望时间+某个$\varepsilon$”定义，它们都将会是等价的。于是我们可以这样定义：

对于概率图灵机$\mathbb{P}$，如果时间函数$T$满足$\forall x$，$\mathbb{P}(x)$以Bounded-error $1/6$计算成功（也即以大于$2/3$概率计算成功）的所有可能计算步数都不超过$cT(|x|)$，就称$L\in \text{BPTIME}(T(n))$。$\text{BPP}=\bigcup\limits_{c>0}\text{BPTIME}(n^c)$，称为有界误差概率多项式类(Bounded-error Probabilistic Polynomial time complexity class)。

$\text{BPP}$可能是概率图灵机定义的最重要的复杂性类了，因为就像人们普遍相信$\text{P}\neq\text{NP}$一样，人们普遍相信$\text{BPP}=\text{P}$（还没有人证明）。这是因为Impagliazzo & Wigderson证明了如果$\text{P}\neq \text{BPP}$，那么SAT就一定有$2^{o(n)}$大小的电路解。而人们普遍相信SAT是难的而不是简单的。如果$\text{BPP}=\text{P}$成立，那么随机算法在理论上看就是一个骗局。不过，从应用上看，随机算法还是有很大价值的。

根据定义，显然有$\text{BPP}=\overline{\text{BPP}}$，并且有上下界$\text{P}\subseteq \text{BPP}\subseteq \text{PP}$。

关于为什么在$\text{BPP}$的定义中能够把$\varepsilon$换作任意值的定义，我们有以下错误压缩定理(Bounded Error Theorem)：

令$\text{BPP}(\rho)$表示以出错概率$\rho$定义的$\text{BPP}$类。错误压缩定理指出，$\forall c,d>1,\text{BPP}(\dfrac{1}{2^{n^d}})=\text{BPP}(\dfrac{1}{2}-\dfrac{1}{n^c})$。这意味着，不仅我们可以用任意常数$\varepsilon$定义$\text{BPP}$，bounded error甚至可以以多项式倒数的速率接近$0$，以指数的倒数的速率接近$1/2$（也即出错的概率可以以多项式倒数的速率接近$1/2$，以指数的倒数的速率接近$0$）。Pf. 显然有$\text{BPP}(\dfrac{1}{2^{n^d}})\subseteq\text{BPP}(\dfrac{1}{2}-\dfrac{1}{n^c})$。因此只需证$\text{BPP}(\dfrac{1}{2}-\dfrac{1}{n^c})\subseteq \text{BPP}(\dfrac{1}{2^{n^d}})$。 也即，$\forall L \in \text{BPP}(\dfrac{1}{2}-\dfrac{1}{n^c}), L\in\text{BPP}(\dfrac{1}{2^{n^d}})$。 对于$L \in \text{BPP}(\dfrac{1}{2}-\dfrac{1}{n^c})$，存在一台概率图灵机$\mathbb{P}$，在输入$x$时，能够以小于$\dfrac{1}{2}-\dfrac{1}{|x|^c}$的出错概率判定$x\in L$是否成立。我们利用多数原则（Majority Rule, 多次实验取众数）的方法，运行$\mathbb{P}'$程序$k$次，得到$k$个判定结果$y_1,\cdots,y_k$，那么可以构造概率图灵机$\mathbb{P}'$，如果超过$k/2$的判定结果为$x\in L$，就输出$x\in L$，否则输出$x\not\in L$。我们分析$\mathbb{P}'$的出错概率。若$\mathbb{P}'$出错，要么是$x\in L$而$\mathbb{P}'$输出$x\not\in L$，要么是$x\not\in L$而$\mathbb{P}'$输出$x\in L$。我们可以令$Y_i=\mathbb{1}[y_i=1]$，$Y=\sum\limits_{i=1}^k Y_i$。为了书写方便，令$\delta=\dfrac{1}{|x|^c},p=\dfrac{1}{2}+\delta$。对于第一种情况，出错概率为$\Pr\left[Y\leq k/2\right]$，由于$\delta<1/2$，所以$(1-\delta)p>1/2$，所以出错概率$<\Pr[Y<(1-\delta)kp]$。因为$x\in L$，所以$\mathbb{E}[Y]\geq kp$，因此出错概率$\leq \Pr[Y<(1-\delta)\mathbb{E}[Y]]$。由Chernoff Bound，并且取$k=12|x|^{2c+d}+1$，得到$<\exp(-\dfrac{1}{2}\delta^2 \mathbb{E}[x])\leq \exp(-\dfrac{1}{2}\delta^2kp)<\dfrac{1}{2^{|x|^d}}$；对于第二种情况，出错概率为$\Pr\left[Y> k/2\right]$，由于$\delta<1/2$，所以$(1+\delta)(1-p)<1/2$，所以出错概率$<\Pr[Y>(1+\delta)k(1-p)]$。因为$x\not\in L$，所以$\mathbb{E}[Y]< k(1-p)$，因此出错概率$\leq \Pr[Y>(1+\delta)\mathbb{E}[Y]]$。由Chernoff Bound，取$k=12|x|^{2c+d}+1$，$<\exp(-\dfrac{1}{3}\delta^2 \mathbb{E}[Y])\leq \exp(-\dfrac{1}{2}\delta^2k(1-p)))<\dfrac{1}{2^{|x|^d}}$； 综上，$L\in \text{BPP}(\dfrac{1}{2^{n^d}})$。Qed.

利用错误压缩定理，可以得到以下几个重要结论：

Adleman定理：$\text{BPP}\subseteq \text{P}_{/\text{poly}}$。“非一致性强于随机性”。

Sipser-Gacs定理：$\text{BPP}\subseteq \Sigma_2^p$。$\text{BPP}$位于多项式谱系的第二层。

$\text{BPP}^\text{BPP}=\text{BPP}$：直观上，因为$\text{BPP}$的出错概率可以压缩到很小，作为oracle调用产生的错误概率可以忽略不计。

零误差概率多项式类(ZPP)

像快速排序这样的随机算法总是会以$1$的概率给出结果，它出错的概率是$0$。对于这类用随机算法零误差解决的问题，我们也可以定义复杂性类。注意到在以下定义中，我们用的是平均时间而不是最坏时间，可见我们牺牲了时间换来了正确性。

对于问题$L$和概率图灵机$\mathbb{P}$，如果时间函数$T$满足$\forall x$，$\mathbb{P}(x)$以零误差计算成功的所有可能计算步数的期望不超过$cT(|x|)$，就称$L\in \text{ZTIME}(T(n))$。定义$\text{ZPP}=\bigcup\limits_{c>0}\text{ZTIME}(n^c)$，称为零误差概率多项式类(Zero-sided-error Probabilistic Polynomial time complexity class)，它包含所有概率图灵机在期望多项式时间内能以零误差判定的问题。

单侧误差概率多项式类(RP)

实践中还会遇到这样一类算法，它能够保证在输出$0$时零误差，而在输出$1$时有概率出错。换言之，这类算法只可能有单侧误差(One-sided Error)。对于这类问题，我们也可以定义复杂性类。注意到在以下定义中，我们用的是Bounded Error，并且是用最坏时间定义的。

对于问题$L$和概率图灵机$\mathbb{P}$，如果时间函数$T$满足$\forall x$，$\mathbb{P}(x)$以单侧误差计算成功的所有可能计算步数的最坏步数不超过$cT(|x|)$，就称$L\in \text{RTIME}(T(n))$。其中，单侧误差计算成功定义为，$\forall x$，如果$x\not\in L$则$\Pr[\mathbb{P}(x)=1]=0$；如果$x\in L$则$\Pr[\mathbb{P}(x)=1]\geq 2/3$。定义$\text{RP}=\bigcup\limits_{c>0}\text{RTIME}(n^c)$，称为单侧误差概率多项式类或随机多项式类(Randomized Probabilistic Polynomial time complexity class)。

根据定义，显然有$\text{RP}\subseteq \text{BPP}$。

可以证明，$\text{ZPP}=\text{RP}\cap \overline{\text{RP}}$。

单侧误差概率对数空间类(RL)

类似的，概率图灵机在对数空间内可以单侧误差判定的问题类称为单侧误差概率对数空间类或随机对数空间类(Randomized Logspace complexity class)。

无向图的连通性判定问题UPATH $\in \text{RL}$。可以用随机游走证明。

可以证明，$\text{RL}\subseteq \text{NL}$。