复杂性类 ZPP

ZPP 中的随机性只影响何时得到答案，不影响答案真伪：算法可在不确定时继续随机尝试，直到获得足以保证答案的证据，但只要求期望多项式时间。它等价于同时具有 RP 与 coRP 算法，因为两个单侧错误方向可以交错运行并互相验证，谁先给出确定结论就停止。零错误不等于每条随机路径都在多项式步内结束；少数路径可以很长，只要期望受控且以概率 $1$ 最终停止。

Las Vegas 快速排序总输出正确排序，随机性只影响比较次数，期望为 $O(n\log n)$，是零错误期望多项式算法的典型形态；但 ZPP 是语言判定类，需要把这类算法放入决策问题模型。若某算法每轮以至少 $1/2$ 获得可验证答案，否则重试，则轮数服从几何分布，期望常数。期望多项式仍不等于每条随机路径都多项式。

固定时间后强制猜一个答案会引入误差，不能继续称为 ZPP；但用 Markov 不等式截断并在超时输出“失败”可转成带失败符号的算法。期望多项式也必须对每个输入成立，而非只对输入分布平均。

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

它由 RP公理库复杂度类 RPComplexity class RP具有单边误差多项式时间随机算法的语言类。、coRP 和 期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。 共同刻画，并包含于 BPP公理库复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。。零错误范式常出现在哈希、几何与数论算法中；概率放大和重启分析则解释如何从单次成功下界推导期望运行时间。