ZPP (复杂度)

在计算复杂度理论内, 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（参见时间谱系理论）。

外部链接