计算复杂度理论内, 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的定义是基于概率图灵机。其他基于概率图灵机的复杂度类包含了BPPRP。至于BQP (复杂度)这个复杂度类则换成使用了量子电脑这种也是具有随机性的电脑。

以交集定义

编辑

ZPP这个复杂度类正好完全相等于RPCo-RP这两个类别的交集。这也是一个常用的ZPP的定义。为了展示这个定义,首先得注意同时在'RPco-RP的每个问题均有个拉斯维加斯算法,如下:

  • 假设我们有一个由RP算法A和(可能完全不同的)co-RP算法B识别的L语言。
  • 给一个输入到L里面,让A演算输入。如果传回“是”,则答案一定是“是”。而让B演算输入,如果传回“否”,答案必是“否”。如果两者皆未发生,则重复这一步骤。

注意到只有一部机器会给出错误答案,而两部机器在回答时给出错误答案的几率几乎是50%。

证据与证明

编辑

与其他复杂度类的关系

编辑

既然ZPP = RPcoRPZPP自然包含在RPcoRP里面。

复杂度类P包含在ZPP里面,有一些人猜想P = ZPP,换句话说,所有的拉斯维加斯算法都有一个等同的决定型多项式时间算法。

如果证明了ZPP = EXPTIME(虽然这猜想几乎是不可能的)将代表PZPP,因为PEXPTIME(参见时间谱系理论)。

外部链接

编辑