想试试看自己能不能写出民科一样的文风.

掷色子, 投硬币可以说是最先进入意识中的随机事件, 一方面上随机方法让我们拥有了一种可以同时审视所有情况的方法, 另一方面随机方法也给了常规非随即方法一种新的审视方法.

切尔诺夫界

如果 \(X_{1}, .., X_{n}\)\(\{0,1\}\) 上两两独立的随机变量, 且 \(\mu = \sum_{i=1}^{n}E(X_{i})\) , 那么对于任意的\(\delta >0\)

\[P\{\sum_{i=1}^{n}X_{i} \geq (1 + \delta)\mu\} \leq (\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}})^{\mu}\]
\[P\{\sum_{i=1}^{n}X_{i} \geq (1 - \delta)\mu\} \leq (\frac{e^{\delta}}{(1-\delta)^{(1-\delta)}})^{\mu}\]

其推论 $$P{|\sum_{i=1}^{n}X_{i} - \mu| \geq c\mu } \leq 2e^{-\min {c^{2}/4, c/2}\mu } $$

等号右侧可以视为一个关于\(c\)的指数函数, 这将会给假设检验提供指数般的下降能力. 也就是说, 在进行建设检验的时候, 验证命题的正确, 如果构造合理, 可以只使用\(log\)级别的数据量.

Bounded Error

作为上面例子的直接应用, 如果我们拥有一枚朝上概率为\(\rho\)的硬币, 其中 \(\rho > \frac{1}{2}\), 那么对于任意的 \(p=1 - \frac{1}{2^n}\) , 我们都可以在 \(O(\log n)\) 的时间内得到这样一枚硬币.

\(\operatorname{BPP}\)

\(\operatorname{BPTIME}(O(f(x)))\) 代表了能在\(O(f(x))\)的概率图灵机上判定的问题的集合. \(\operatorname{BPP} = \bigcup_{i = 0} ^ {\inf}\) \(\operatorname{BPTIME}(n^{i})\) 则代表在概率意义下 \(\operatorname{P}\) 的对应类.

值得注意的是, 这里的运行时间, 是对于所有可能下的最坏运行时间, 而决定这样一个概率图灵机是否接受一个字符串取决于所有可能的转移之下, 接受的概率大还是拒绝的概率大, 当然由于 Bounded error 的情况下, 这里的概率只需要大于 \(\frac{1}{2}\) 就好了.

如果接受的概率定义如此"松", 那么对于运行时间呢, 实际上如果将最坏时间替换为期望时间也不会产生 \(\operatorname{BPP}\) 发生变化, 当然从这里就能简单窥探出概率图灵机与非确定性图灵机的区别, 虽然它们都具有审视所有可能情况的能力, 但概率性图灵机限定了期望的运行时间.

同时概率图灵机接受输入, 取决于接受的情况是多是少, 而并非只有一个接受情况.

很容易验证出 \(\operatorname{P} \subset \operatorname{BPP}\) , 但是否相等仍然是OPEN的.

当然由于简单的定义,很容易得到 \(\operatorname{BPP} \subset \operatorname{EXP}\) , 因为可以在指数时间之内枚举所有的随机选择.

Derandomize

前文提到了在常规算法设计中引入概率, 可以改变审视算法的观点, 例如可以在期望\(O(n)\)的时间内得到一个数列的第\(k\)大, 例如可以在期望多项式时间内判定质数, 虽然前两个问题都存在更优秀的在确定性图灵机下的对应方法, 但都显得更加复杂.

除此之外也有更多已被证明属于 \(\operatorname{BPP}\) , 而不知道是否属于 \(\operatorname{P}\) 的问题, 例如检验一个多项式是否恒为0.

即使如此人们仍然相信 \(\operatorname{P} = \operatorname{BPP}\), 或许是因为对于一些简单的概率算法, 存在可以简单构造出的确定性算法. 例如对于Set Cover 存在一个近似度为 \(O(\ln n)\) 的算法, 基于概率对LP中的变量进行随机赋值. 可以很简单的通过期望, 来反推出每个决策变量是多少, 这个过程就叫做 Derandomize.

RP and coRP

为了探索 \(\operatorname{P}\)\(\operatorname{BPP}\) 之间的 gap , 可以更加收紧 \(\operatorname{BPP}\) 的定义, 例如使之在错误的概率变成 0, 使之成为 \(\operatorname{RP}\) , 同样形成 \(\operatorname{coRP}\) , 有意思的是 $\operatorname{ZPP} = \operatorname{RP} \bigcap \operatorname{coRP} $

Key

一个随机图灵机可以转化成一个除一般的输入之外还有一个输入的串不妨把它叫做 key 吧, 我也不知道应该叫作什么, 这个 key 决定了整个随机过程.

在这样的定义之下, 可以证明出 \(\operatorname{BPP} \subset \operatorname{P_{/poly}}\)\(\operatorname{BPP} \subset \operatorname{PH}\) , 更进一步有 \(\operatorname{BPP} \subset \operatorname{\sum_{2}^{P}} \bigcup \operatorname{\Pi_{2}^{P}}\) . 它起码存在于多项式分级之中了, 但由于 \(\operatorname{BPP}\) 基于语义的定义, 让 \(\operatorname{BPP}\) 层的完全问题比较难以找到, 也让这个层级的发展有了一些困难.

交互式证明

零知识证明是交互式证明中的一个小部分, 零知识证明可以让我们看到一个能力不强的个体, 如果可以跟一个能力更强的个体交互, 便能获得一个比较强的能力.

当让受制于交互的形式, 获得的能力也不一样, 例如如果一个普通的图灵机与一个能力极强的个体交互, 这里的个体可以突破图灵机的限制, 这样一种交互的形式可以产生\(\operatorname{dIP}\)类, 可以发现如果对于 \(\operatorname{NP}\) 的语言, 由于可以提供一个短证明, 那么便可以在一轮之内完成交互, 而对于任意一个多项式交互回合, 可以利用非确定性图灵机猜出交互过程, 于是便可以得到 \(\operatorname{dIP} = \operatorname{NP}\). 这个结果可能有点令人失望.

但幸运的是如果我们将普通的图灵机替换成概率图灵机, 便可以让能力提升到\(\operatorname{PSPACE}\) , 即 \(\operatorname{IP} = \operatorname{PSPACE}\) .

所以如果有了一个色子, 能否增强机器的能力仍然有待商榷, 而且色子也无法让我们审视全部的答案. 但如果色子无法可以带来巨大的提高, 那无异于说明了寻找理想的噪声是无意义的.