ZPP (复杂度)
 | 此条目没有列出任何参考或来源。 (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（参见时间谱系理论）。
外部链接[编辑]
| ||||||||||||||||||||||||||||||||||||
