Computational Complexity: Randomized Computation

Probabilistic Turing Machine

$\textbf{PTM}$是$\textbf{NDTM}$的升级，其以确定的概率（一般均为0.5）选择$\delta _0$和$\delta _1$。故概率图灵机的输出$\mathbb{P}(x)$是一个随机分布（变量）。$
\text{Pr}[\mathbb{P}(x)=y]$表示给定输入$x$，该概率图灵机输出$y$的概率。

一个函数$\phi$是概率可计算的（能被概率图灵机$\mathbb{P}$计算），若：

$$
\phi(x)=
\begin{cases}
y,\text{if}\space \text{Pr}[\mathbb{P}(x)=y] > 1/2 \\
\uparrow, \text{if no such y exists}
\end{cases}
$$

一个语言$L$能被$\textbf{PTM}$判定，当且仅当：

$$
\text{Pr}[\mathbb{P}(x)=L(x)] > 1/2
$$

概率图灵机可计算的函数就是可计算函数。

Average Case Time Complexity

概率图灵机可以定义平均时间复杂性。

With bounded error:

$$
\phi(x)=
\begin{cases}
y,\text{if}\space \text{Pr}[\mathbb{P}(x)=y] \ge 1/2 + \epsilon \\
\uparrow, \text{if no such y exists}
\end{cases}
$$

带bounded error是为了避免出现任何问题都能平均两步解决的错误结论。

Polynomial Identity Testing

著名随机算法——等价性测试：测试两个电路是否是等价的。

在有限域中随机取值，直接输入该电路。

$\textbf{PP}$

若$\forall x \in \{0,1\} ^*$，$\text{Pr}[\mathbb{P}(x)=L(x)] > 1/2$，且对任意的选择，$\mathbb{P}$在$T(|x|)$步内停机，则$\mathbb{P}$在$T(n)$时间内判定$L$。（$T$为最坏时间复杂性）

上面的定义即为$\textbf{PP}$类，其等价定义为：有个多项式时间的普通图灵机$\mathbb{M}$，使得：

$$
\text{Pr} _{r \in \{0,1\} ^{p(|x|)}}[\mathbb{M}(x,r)=L(x)] > 1/2
$$

其中$r$为一个随机串。

$$
\textbf{NP},\text{co}\textbf{NP} \subseteq \textbf{PP} \subseteq \textbf{PSPACE}
$$

PP完全

都是$\textbf{SAT}$的变形。

$\phi \in \text{MajSAT}$如果有超过一半的真值指派，使得$\phi=1$。

C-L归约，$\delta$的选择转变为一个个真值指派。

$\textbf{PP}$是封闭的，所以对$A \in \textbf{PP}$，$B \in \textbf{PP}$，有$A\cap B \in \textbf{PP}$，$A \cup B \in \textbf{PP}$。

$\textbf{BPP}$

B：Bounded-Error

接受标准：With bounded-error，即要严格大于$1/2$。时间复杂度：最坏时间复杂度与平均时间复杂度都行（马尔可夫不等式），两者定义出来的是等价的。$\textbf{BPP}$一般用的标准是$2/3$。

$$
\textbf{P} \subseteq \textbf{BPP} \subseteq \textbf{PP}
$$

$$
\textbf{BPP}= \textbf{coBPP}
$$

$\textbf{BPP}$是很鲁棒的，出错概率大和出错概率小的$\textbf{BPP}$定义的是同一个类。（出错概率高，则多运行几次，取出现多的为最终值）。

错误压缩定理：可以把错误压缩到指数的倒数。

带神谕的BPP

$$
\textbf{BPP} ^{\textbf{BPP}} = \textbf{BPP}
$$

错误压缩，让子程序的调用几乎不出错。

$\textbf{BPP}$完全

不存在。如果$\textbf{BPP}=\textbf{P}$，则存在。

Adleman Theorem：

$$
\textbf{BPP} \subseteq \textbf{P} _{\text{poly}}
$$

定理：

$$
\textbf{BPP} \subseteq \Sigma _2 ^p \cap \Pi _2 ^p
$$

用错误压缩定理证明。

$\textbf{ZPP}$

平均运行时间为P且不出错的概率图灵机：

$$
\textbf{ZPP}=\bigcup _{c \in \text{N}}\textbf{ZTIME}(n ^c)
$$

如一些排序算法

$L \in \textbf{ZPP}$等价于存在最坏时间为$\textbf{P}$的概率图灵机，其在多项式时间内输出$\{0,1,?\}$，其中$?$表示算不出来，要求算不出来的概率小于等于1/3。

单向出错算法：回答是一定对，回答否可能错。

多项式时间的单向出错算法：
$$
\textbf{RP}=\bigcup _{c \in \text{N}} \textbf{RTIME}(n ^c)
$$

其与$\textbf{ZPP}$存在关系：

$$
\textbf{ZPP}=\textbf{RP}\cap \textbf{coRP}
$$

左到右：若让$?$是始终回答NO，则ZPP就是RP；若始终回答YES，则ZPP就是coRP；
右到左：RP回答YES一定是对的，coRP回答NO一定是对的，因此交叉运行两个算法即可。

RP也有错误压缩定理。类似地，ZPP也有错误压缩定理。