在计算复杂度理论内, ZPP（zero-error probabilistic polynomial time，零错误概率多项式时间）是一个与机率图灵机有关的的复杂度类。
简介在计算复杂度理论内, 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 (复杂度)**这个复杂度类则换成使用了量子电脑这种也是具有随机性的电脑。1
以交集定义ZPP这个复杂度类正好完全相等于RP和Co-RP这两个类别的交集。这也是一个常用的ZPP的定义。为了展示这个定义，首先得注意同时在'RP和co-RP的每个问题均有个拉斯维加斯算法，如下：
假设我们有一个由RP算法A和（可能完全不同的）co-RP算法B辨识的L语言。
给一个输入到L里面，让A演算输入。如果传回“是”，则答案一定是“是”。而让B演算输入，如果传回“否”，答案必是“否”。如果两者皆未发生，则重复这一步骤。
注意到只有一部机器会给出错误答案，而两部机器在回答时给出错误答案的机率几乎是50%。1
与其他复杂度类的关联既然ZPP=RP∩coRP，ZPP自然包含在RP和coRP里面。
复杂度类P包含在ZPP里面，有一些人猜想P=ZPP，换句话说，所有的拉斯维加斯算法都有一个等同的决定型多项式时间算法。
如果证明了ZPP=EXPTIME（虽然这猜想几乎是不可能的）将代表P≠ZPP，因为P≠EXPTIME（参见时间谱系理论）。1
本词条内容贡献者为:
李嘉骞 - 博士 - 同济大学