形式陈述

语言 $L$ 属于 ZPP，若存在随机算法始终输出正确答案，且对每个输入的期望运行时间为多项式。等价地，

$$\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{coRP}.$$

也可用 Las Vegas 算法表述：算法可能因随机选择运行较久，但从不输出错误判定。

直觉

随机性只影响何时得到答案，不影响答案真伪；RP 与 coRP 两个单侧错误方向相交后可以互相验证并消除错误。

例子与边界

随机快速排序是零错误期望多项式算法，但 ZPP 是语言判定类，需要把算法放入决策问题模型。期望多项式不等于每条随机路径都多项式。

推论与应用

它厘清 Las Vegas 与 Monte Carlo 随机化，并完善 P、RP、coRP、BPP 之间的包含图。

参考资料

• Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach (2009), randomized complexity.
• John Gill, Computational Complexity of Probabilistic Turing Machines (1977), probabilistic Turing machines.