随机性可以使算法变快,同时不允许其给出错误答案。这样的算法有时可能比通常情形花费长得多的时间,因此最坏情形的时间界并不是恰当的度量。另一种做法是坚持固定的时间限制,并允许算法回答“未知”。这两种观点引出了类 ZPP,并解释了它与单侧随机判定过程之间的关系。
我们讨论语言 ,且随机比特是独立且均匀地抽取的。下文所有关于概率和期望的陈述都是针对每个固定输入 而言的;不假设任何输入分布。随机化机器的运行时间 计入所有步骤,包括生成随机比特。多项式期望时间界是指存在一个多项式 ,使得对每个输入 都有 。 可将 增大,使得对每个 都有 。
零错误与可变运行时间
定义 1.2.1
(Las Vegas 判定器与 ZPP)
语言 的 Las Vegas 判定器满足:在每条终止的计算路径上输出正确的成员判定比特,对每个输入以概率一停机,并且对每个输入具有多项式期望运行时间。我们将 定义为具有这类判定器的语言的集合。“期望”一词并不保证所有路径都在多项式时间内结束。该界必须对每个固定长度的所有输入一致成立。一条概率为零的无穷随机序列不影响几乎必然终止,但机器确实停机的每一条有限路径上都必须给出正确答案。
例题 1.2.2
(重复投掷公平硬币及其运行时间)
考虑这样一个过程:反复投掷一枚公平硬币直到第一次出现正面,然后返回一个预先确定的正确答案。令 为投掷次数。对 ,事件 表示前 次投掷均为反面,其概率为 。恒等式 逐点成立;对其非负各项取期望,得 。该过程以概率一停机,尽管对每个固定的 ,它都有正概率 需要多于 次投掷。假想的无穷全反面序列概率为零。这个玩具过程用来说明资源上的区别;它的答案是预先给定的,因此它并不是针对任意语言的算法。
常见错误
(多项式期望时间不等于多项式截断)
期望是对同一输入上随机选择的平均值所作的界。它允许出现罕见的长时间运行。反过来,一台总是很快停机但有时给出错误答案的机器并不自动是零错误的。运行时间与正确性是两个独立的要求;“未知”的输出既不是“是”的回答,也不是“否”的回答。
定义 1.2.3
(RP 与 coRP)
我们还使用标准的单侧类。若存在多项式时间随机化判定器,对“是”实例以至少 的概率接受,且从不接受“否”实例,则语言 属于 RP。若其补语言属于 RP,则 属于 coRP:coRP 判定器从不拒绝“是”实例,并以至少 的概率拒绝“否”实例。每一次随机选择和概率界都是针对给定输入上机器的硬币而言的。重复独立试验可以降低所允许的单侧错误的概率,而不会在另一侧产生错误。
例题 1.2.4
(理解单侧保证的方向)
设某语言的一个随机化多项式时间检验以概率 接受真实例,并以概率零接受假实例。它是一个 RP 过程:接受可证明成员关系,而拒绝则可能没有结论。用新的硬币运行两次,只要任一次接受就接受,则在真实例上的假阴性概率至多为 ,且仍然没有假阳性。如果两次运行重用相同的硬币,它们的失败可能完全相同,平方就没有道理。
将期望时间转化为“未知”答案
关键的估计是 Markov 不等式。对于非负随机变量 和 ,有 。我们以下面的形式使用它,并直接证明这一形式,而不是引入某个集中不等式定理。
命题 1.2.5
(非负运行时间的截断)
若非负随机变量 具有有限期望且 ,则 。
证明
(用示性函数比较证明 Markov 不等式)
逐点地有 。取期望得 。除以正数 即得该界。只要期望有限,无论运行时间分布的可能取值集合是有限还是无限,它都成立。
例题 1.2.6
(截断一个可变时间的判定器)
设一个正确的随机化判定器在长度为 的输入上期望运行时间至多为 。在 步后停止它(必要时将截断点向上取整),若尚未停机则输出“未知”。由 Markov 不等式,到达截断点而没有结果的概率至多为 ;关于恰在最后一步停机的具体约定只会改进此界。新的过程总在多项式步数内停机,只要输出比特则该比特正确,并且以至少 的概率给出该答案。检查截断点的时间只增加多项式开销。
截断使用的是某个特定的多项式界,它属于 Las Vegas 机器存在性证明的一部分。算法无需从单次执行中推断自身的期望运行时间。不同的构造中可以固化不同的多项式界,而有限多个较小的输入长度可以通过增大多项式来处理。
两个单侧过程给出零错误
定理 1.2.7
(零错误的刻画)
。
证明
(两个方向各自的模拟)
首先设 ,并取一个期望时间至多为 的 Las Vegas 判定器。让它运行 步。为得到 RP 判定器,仅当模拟已停机并且在截断点之前返回“是”时才接受;否则拒绝。“否”实例永远不会被接受,因为任何返回的答案都是正确的。在“是”实例上,由截断估计,正确的“是”答案以至少 的概率出现,超过所要求的 。时间是多项式的。
对于 coRP 判定器,使用同样的有界模拟,但仅当它已停机并返回“否”时才拒绝;否则接受。它从不拒绝“是”实例,并以至少 的概率拒绝“否”实例。因此 属于这两个类。这两种变换将“未知”映射为相反的答案,因为所允许的错误位于相反的两侧。
反之,设 有一个 RP 判定器 和一个 coRP 判定器 。在每一轮中,用新的随机比特运行 。若 接受,则输出“是”。若它拒绝,则用新的随机比特运行 ;若 拒绝,则输出“否”。否则以独立的硬币开始新的一轮。 和 的每次运行都花费多项式时间。
在“是”实例上, 从不拒绝,而 在每一轮中以至少 的概率接受。到达第 轮的概率至多为 ,期望轮数至多为 。在“否”实例上, 从不接受,而 在每一轮中以至少 的概率拒绝,给出相同的尾部界和期望界。该过程仅当 证明“是”时才可能输出“是”,仅当 证明“否”时才可能输出“否”,因此它从不输出错误答案。它几乎必然终止,且具有多项式期望时间,从而证明 。
证明透视
两个单侧类如何互相提供证书
两个方向各依赖一个想法。对于 ,不显然的一步是:同一个截断模拟可以给出两个不同的判定器,区别只在“未知”被送到哪一边:对 RP 是拒绝,对 coRP 是接受。这样做是安全的,因为返回的比特必然正确,所以唯一可能的错误就是“未知”的结果,而每个错误都落在该类所允许的一边;Markov 截断把它们的概率限制在 。反方向则是: 只能证实“是”, 只能证实“否”,而循环只在得到证书时才输出,所以无论硬币怎样落下都不会输出错误的比特。概率只在终止性上起作用:每一轮都使用全新的硬币,使给定过去后失败的概率至多为 ,从而得到尾部 。若只有 ,“否”实例永远得不到证书,循环就可能永不停止,这就是两个类都需要的原因。
一轮之内 与 的先后顺序属于实现上的选择,并不改变证明。关键在于:“是”证书不可能出现在“否”实例上,“否”证书不可能出现在“是”实例上,并且每一轮都有固定的正概率产生相应的证书。尾部界使用了各轮之间新的独立随机性;若没有这一条件,反复失败可能保持完全相关。
例题 1.2.8
(固定输入上的一个单侧对)
设在某个特定的“是”实例上, 以概率 接受,而 如可靠性所要求的那样总是接受。零错误过程在 第一次成功运行时返回“是”,并且从不返回“否”。需要多于三轮的概率为 ,期望轮数为二。在“否”实例上角色互换: 总是拒绝,而 的拒绝结果提供了正确的“否”答案。这些数值只是对一个输入说明证明;类的成员资格要求存在一对多项式时间算法,使其保证对每个输入都成立。
有界时间的表述
将前面的想法打包成这样一个算法往往很方便:它输出“是”、“否”或“未知”,总在多项式时间内运行,从不输出错误的比特,并且对每个输入以至少 的概率输出一个比特。这样的算法给出一个 ZPP 判定器:独立运行多个副本,直到某一个返回比特。若每次试验至多花费 步,则失败多于 次的概率至多为 ,因此期望总时间至多为 加上多项式的准备开销。所有返回的比特都是正确的,且几乎必然终止。
反之,Markov 截断构造把任何 ZPP 判定器转化为这样的有界时间三输出算法,其成功概率至少为 。这是一种带有明确的逐输入成功保证的表述等价。若某个过程在某个输入上可能永远输出“未知”,或仅在某个选定的输入分布上平均而言才成功,则不满足所述定义。
命题 1.2.9
(零错误蕴含有界错误)
且 。
证明
(两次独立运行)
第一组包含关系由上述刻画得出。对于 RP,独立运行判定器两次,只要至少有一次接受就接受。在“否”实例上接受概率为零;在“是”实例上失败概率至多为 。这满足通常的 BPP 阈值。对于 coRP,独立运行两个副本,只要至少有一个拒绝就拒绝;对称的论证给出至多 的错误。这些包含关系并不能确立其中任何类互不相同,或等于 。
常见错误
(正确性并不限定时间)
一台机器可以在停机时总是输出正确比特,却仍不是 ZPP 判定器:例如,它可能在某个输入上以概率 循环,或者几乎必然停机但期望运行时间无穷。定义要求既几乎必然终止,又具有多项式期望界。类似地,该多项式期望必须对给定长度的每个输入成立,而不仅仅是对各输入取平均之后成立。
反例模式
几乎必然终止并不给出多项式期望时间
一个诱人的说法是:只要一台正确的机器在每个输入上以概率一停机,它的期望运行时间就已经有限,因而有多项式界。设运行时间是取正整数值的随机变量 ,对 有 。这些概率之和为一,因为 ,部分和逐项相消,所以 以概率一为有限。然而
因此期望不可能有任何多项式界。ZPP 的定义于是把期望界与几乎必然终止分开要求。此例并不声称存在对此分布的高效采样算法。
练习与解答
快速检查
(一个非负运行时间的期望至多为 。求它至少为 的概率的上界。)
在截断命题中取 。
解答 · 答案
由 Markov 不等式,。
快速检查
(若产生“未知”的试验在每次独立重复中成功的概率都至少为 ,求连续三次失败的概率的上界。)
独立试验的失败概率相乘。
解答 · 答案
由独立性,概率至多为 。
快速检查
(为什么由零错误模拟构造出的 RP 判定器在超时时拒绝?)
RP 判定器允许在哪一侧出错?
解答 · 答案
超时没有结论。RP 允许以有界概率拒绝“是”实例,但绝不允许接受“否”实例;在超时时拒绝遵守了这一方向。
快速检查
(为什么在 RP/coRP 构造的每一轮中都需要新的随机带?)
想一想给定前面各轮后,一轮失败的条件概率是多少。
解答 · 答案
独立的新随机带使每一轮中失败的条件概率至多为 ,从而得到几何型尾部。重用同一条随机带可能使同一个失败结果永远重复。
快速检查
(若一台零错误机器几乎必然停机,但在某个输入上期望时间无穷,它是否满足此处使用的 ZPP 定义?)
比较定义中的两项要求。
解答 · 答案
不满足。仅有几乎必然终止并不能提供所要求的多项式期望时间界。
快速检查
(等式 是否证明了 ?)
这个等式把哪个类等同于交集?
解答 · 答案
不能。该等式只是把交集等同于 ZPP。它本身并不说明这两个单侧类是否重合。