固定的是输入,随机的是算法的抛币
随机算法对同一输入可能给出不同答案。正确性陈述必须交代:哪种答案可能错、错误概率多大,以及概率取自哪里。这些细节决定怎样重复才安全。“只要有一次接受就接受”很适合某些单边错误测试,却可以让双边错误测试更不可靠。
我们研究以语言 表示的判定问题; 就是肯定实例。本节的每个错误概率都是:先固定任意输入,再对算法的公平随机比特取概率。我们没有假设输入服从某种分布。
三种不同的正确性保证
定义 7.1.1
(多项式时间随机判定算法)
算法 接收输入 与随机带 。对每个长度为 的输入及每条随机带,运行时间都有同一个多项式上界,故所用随机比特也至多有多项式个 。把未用比特补齐,让同一输入长度的带等长,再均匀选取。
下表是算法识别 时的保证:
| 类别 | 若 | 若 |
|---|---|---|
| RP | 接受概率至少 | 绝不接受 |
| coRP | 必定接受 | 接受概率至多 |
| BPP | 接受概率至少 | 接受概率至多 |
若存在符合某行保证的算法,语言便属于该类别。这里的时间界是对随机带取最坏情形,不只是期望时间界。
RP 的接受答案可以确定输入是肯定实例;拒绝则可能只是本次随机试验错过见证。coRP 相反,拒绝可以确定是否定实例。BPP 的两种答案都可能错。这些条件不允许算法只在大部分输入上正确:每个单独输入都必须符合所在行的界。
表中的常数是方便的基准。放大真正需要的是失败概率与相关阈值之间留有合适差距。下面直接证明这些常数下的界,不把任何重复过程都当成自动有效。
RP 放大要保留确定正确的答案
用独立的新随机带运行 RP 算法 次,至少一次接受就接受。否定实例每次都拒绝,所以仍不会错误接受。固定肯定实例,设单次拒绝概率为 ;重复过程出错,必须全部 次都拒绝。由独立性,
要把错误降至 ,取 即可。时间与随机比特用量都增加 倍。
例题 7.1.2
(具有单边错误的小型抽样测试)
输入有四个比特,问题是是否至少一位为 1。一次试验独立且均匀地有放回抽取三个索引;只要抽到 1 就接受。全零输入不可能被接受。有至少一位 1 时,最坏情况恰有一位 1,因此拒绝概率为
所以这个固定大小例子符合 RP 的错误保证。对 0010,接受概率为 。两次独立的三抽样试验用 OR 合并,漏掉该 1 的概率为 。
这是用来看清保证的例子,没有宣称加速:直接读完四位,就可以确定性地解决这个小问题。
coRP 用对偶规则:全部 次都接受才接受。肯定实例仍必定接受,否定实例的错误接受概率则至多 。
两次重复已足以把任一单边类别放进 BPP,因为唯一可能的错误至多 。确定性多项式时间算法忽略随机带,就同时符合两种单边保证。把 BPP 算法的输出取反也保留错误界,因此 BPP 对补集封闭。
反例模式
OR 也可以放大错误答案
假设 BPP 算法在某个否定实例上,以 概率接受。若独立运行 次后只要一次接受就接受,错误接受概率变成 ,并趋近 1;三次时已是 。
同样,要求全部接受会破坏肯定实例的保证。若单次接受概率是 ,合并后便是 ,趋近 0。
合并规则必须配合错误保证。只说“重复运行”,还没有指定正确的放大算法。
多数表决处理双边有界错误
BPP 可独立重复奇数次 ,返回多数答案。固定任意输入 ;第 次错时令 ,否则为 0。每次错误概率至多 ,而新随机带彼此独立,故 也独立。多数答案错误,至少要有 次出错。
定理 7.1.3
(初等的指数多数表决错误界)
若 为奇数,独立重复并采用多数表决,则对每个固定输入,
因为 ,此上界随 指数下降。
证明
(用非负指数量检测大量错误)
对非负随机变量 与 ,有 :在事件 上,对期望的贡献至少是 乘该事件概率。这就是 Markov 不等式。
记 。多数错误蕴含 ,因此 。若 ,则 。用独立性可得
把期望拆成乘积的等号,正是使用独立性的地方。此证明不需要算法在不同输入上的行为彼此独立。
证明透视
证明在哪里用到各个假设
证明有三个运作部分。底数 使 容易计算,并把 转成 ;换另一个底数会得到另一个常数。错误假设 只通过 进入,所以证明不需要 的精确值。独立性恰好用一次,就是把 拆成乘积;Markov 不等式和逐个因子的上界都不需要它。最后,对错误概率 ,最终指数的底是 ,恰在 时小于 ,所以这个初等计算用到 与该阈值之间的距离。
取不小于下式的奇数 ,即可让上界至多为 :
重复次数为 。特别地,正多项式 所指定的错误 ,可以由 BPP 算法在多项式时间达到。要求任意微小错误并非免费:若 对输入长度已是指数,此放大过程未必仍是多项式时间。
例题 7.1.4
(要运行多少次才能使错误至多 ?)
设要从 BPP 算法得到至多 的错误。上界要求 ,所以最小的奇数取值是 。为看出它有多松,设每次运行的错误概率为 ,取 。精确的多数表决错误为 ,而上界给出 。上界有效但偏保守:它保证的是指数级的下降速率,不是最少的重复次数。
上界不等于实际错误
例题 7.1.5
(三次运行的精确多数表决错误)
为这项计算,假设固定输入上三次独立运行的错误概率都恰为 。这个概率可由有限均匀公平比特带产生,恰为 则不行;BPP 定义把 当上界,没有要求能取等号。错误次数分布如下:
| 错误次数 | 概率 | 多数答案错误? |
|---|---|---|
| 0 | 否 | |
| 1 | 否 | |
| 2 | 是 | |
| 3 | 是 |
实际多数表决错误为 。前述一般指数界对少量试验刻意较松;它证明统一的下降速率,并非精确二项尾概率。
反例模式
复制随机带不会产生新证据
断言:三次各以概率 出错的运行,多数表决错误永远是 。假设某固定输入上,基本算法恰在四分之一随机带上出错,三次运行都使用同一条带。输入与带完全决定计算,三个答案必然相同,所以多数表决恰在单次出错的那些带上出错。错误保持 ,不是 。各次单独都符合错误概率,却因相关而使多数表决界证明中的乘积步骤失效。修正:各次运行使用新而独立的随机带;独立性是放大定理的假设,不只是实现上的外观选择。
同一输入长度的一条好随机带
BPP 保证先固定 ,再对 取概率;它没有说某条抽到的带同时适用于全部输入。不同输入的坏带可能不同。不过,先放大再用有限并集界,就能得到有用的存在性结论。
定理 7.1.6
(一条多项式长度的带可以处理所有长度 n 的输入)
设 。对每个输入长度 ,先把每输入错误放大至至多 。对此放大算法,存在同一条随机带 ,使全部 个长度为 的二进制输入都回答正确。
证明
(用并集界一次计算所有输入)
固定此长度,把放大算法的带补至共同多项式长度 。对每个 ,令 是均匀所选带使算法在 上出错的事件。每事件概率至多 ,所以
并集界不需要这些事件独立。至少以 概率,一条带不属于任何坏事件,因此至少存在一条好带。所需放大只用 次重复,所以 仍是多项式。
概念视角组合
输入与随机带的表格
作一张表格:长度为 的每个输入占一行,每条随机带占一列,算法出错的格子加上标记。每一行中带标记的格子至多占 ,所以含有任何标记的列至多占 。因此至少有一半的列没有标记,而每个没有标记的列,就是对所有输入同时正确的一条随机带。
这给出非均匀结论。
定义 7.1.7
()
语言 属于 ,是指存在多项式 、只依赖输入长度 且长度为 的建议字符串 ,以及确定性多项式时间机器 ,使得 当且仅当 接受。
推论 7.1.8
(BPP 包含于 P/poly)
。
证明
(建议就是那条好随机带)
设 。对每个长度 ,取上一个定理中放大算法的好随机带 作为建议 。确定性多项式时间机器以这条固定的带模拟放大算法处理 。由 的选取,长度为 的每个输入都答对,所以 。
常见错误
(建议不等于去随机化)
量词非常重要:每个长度都存在合适建议。证明没有给出均匀多项式时间过程来找这些建议,因此没有证明 ,也没有说可在所有输入长度重用同一条常数带。建议的存在性与可执行的均匀去随机化算法,是不同结论。
附解答练习
快速检查
(独立抽样与重用抽样结果)
对四位测试输入 0010,计算两次独立三抽样试验用 OR 合并的失败概率。若第二次重用第一次的三个索引,结果如何?
解答 · 答案
单次失败为 ;独立两次同时失败为 。重用索引会看到完全相同比特,所以合并失败仍为 。OR 符合单边保证,但把失败概率相乘仍需要独立。
快速检查
(计算五次多数表决错误)
固定输入,假设五次独立运行的错误概率都恰为 。求精确多数表决错误。若输入是否定实例,改用 OR 的错误接受概率是多少?
解答 · 答案
有三、四或五次错误时,多数答案错误:
否定实例上,每次错误就是接受。OR 只有全部五次都拒绝才不错误接受,所以错误为 。多数表决改善双边错误,此 OR 规则却让它增加。
快速检查
(对全部十位输入作同时保证)
假设共同长度的随机带,对每个十位输入的错误都至多 。求一条带至少在某个十位输入出错的概率上界。不同输入的事件必须独立吗?好带存在仍没有提供什么?
解答 · 答案
共有 个输入。由并集界,至少一个输入出错的概率至多 ,故至少以 概率,带对全部十位输入正确,好带必然存在。不需要跨输入独立。存在性证明没有提供对每个长度均匀且有效地找好带的算法;均匀去随机化主张所欠的正是此步。
快速检查
(平均错误小是另一种保证)
设 是空语言。对长度 ,某确定性算法只接受 ,其余全部拒绝。均匀随机长度 n 输入下的错误为 。它符合空语言的 BPP 保证吗?
解答 · 答案
不符合。固定否定实例 上,它以概率 1 接受。输入分布下平均错误小,不能修补逐输入保证的违反。空语言本身当然属于 P 与 BPP:永远拒绝就正确识别它。失败的是这个提议的算法,而非该语言的类别归属。