ZPP (复杂度)
外观
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此条目没有列出任何参考或来源。 (2023年1月28日) |
在计算复杂度理论内, ZPP(zero-error probabilistic polynomial time,零错误概率多项式时间)是一个与几率图灵机有关的的复杂度类,并且存在以下特点:
- 这机器永远会给出正确的"是"或者"否"的答案。
- 这个机器平均运作的时间是多项式时间以内。
换句话说,有一个算法会在运作时使用一个完美随机的硬币,并且永远回传正确的答案(这种算法被称作拉斯维加斯算法(Las Vegas algorithm))。对一个输入大小为n的问题,存在一个多项式p(n),令平均的运作时间小于p(n)(有可能偶尔会超过)。
另外,ZPP可以定义为一个问题的集合,里面每个问题都存在一个可以解决此问题的几率图灵机,且此机器性质如下:
- 运转时间永远是多项式时间
- 会回传YES,NO或者DO NOT KNOW的答案
- 答案如果不是DO NOT KNOW,就会是正确的答案
- 如果问题的正确答案是YES,这机器回传YES的几率至少是1/2(其他时候回传DO NOT KNOW)
- 如果问题的正确答案是NO,这机器回传NO的几率至少是1/2(其他时候回传DO NOT KNOW)
以上这两个定义是相等的。 ZPP的定义是基于概率图灵机。其他基于概率图灵机的复杂度类包含了BPP和RP。至于BQP (复杂度)这个复杂度类则换成使用了量子电脑这种也是具有随机性的电脑。
以交集定义
[编辑]ZPP这个复杂度类正好完全相等于RP和Co-RP这两个类别的交集。这也是一个常用的ZPP的定义。为了展示这个定义,首先得注意同时在'RP和co-RP的每个问题均有个拉斯维加斯算法,如下:
- 假设我们有一个由RP算法A和(可能完全不同的)co-RP算法B识别的L语言。
- 给一个输入到L里面,让A演算输入。如果传回“是”,则答案一定是“是”。而让B演算输入,如果传回“否”,答案必是“否”。如果两者皆未发生,则重复这一步骤。
注意到只有一部机器会给出错误答案,而两部机器在回答时给出错误答案的几率几乎是50%。
证据与证明
[编辑]与其他复杂度类的关系
[编辑]既然ZPP = RP ∩ coRP,ZPP自然包含在RP和coRP里面。
复杂度类P包含在ZPP里面,有一些人猜想P = ZPP,换句话说,所有的拉斯维加斯算法都有一个等同的决定型多项式时间算法。
如果证明了ZPP = EXPTIME(虽然这猜想几乎是不可能的)将代表P ≠ ZPP,因为P ≠ EXPTIME(参见时间谱系理论)。
外部链接
[编辑]
|