复杂性类 ZPP

允许回答“暂时不知道” ​

另一种等价定义是：存在最坏多项式时间算法 $B$，输出 $0$、$1$ 或失败符号 $\mathrm{\perp }$；输出 $0/1$ 时一定正确，每个输入上 $\text{Pr}(B(x)=\mathrm{\perp })\le 1/2$。

从期望时间定义得到它，只需在 $2p(|x|)$ 步后截断 $A$，未结束就返回 $\mathrm{\perp }$。由Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。，

反过来，用全新的独立随机币反复运行 $B$，遇到 $0/1$ 就返回。对固定输入，一轮成功概率至少 $1/2$，所以轮数的期望至多 $2$，总期望时间仍为多项式。这由几何等待时间理路几何分布Geometric distribution独立同概率 Bernoulli 试验中等待首次成功所需试验次数的分布。得到；失败符号是“本轮没有结论”，不是语言的第三种答案。

为什么 $\mathrm{ZPP}=\mathrm{RP}\cap \mathrm{coRP}$ ​

RP理路复杂度类 RPComplexity class RP具有单边误差多项式时间随机算法的语言类。 算法给出的“接受”是可靠结论：非成员绝不被接受，成员以至少 $1/2$ 的概率被接受。coRP 则反过来：“拒绝”可靠，非成员以至少 $1/2$ 的概率被拒绝，成员绝不被拒绝。

若一个语言同时有这两种算法，每轮分别运行一次。RP 算法接受就输出 $1$；coRP 算法拒绝就输出 $0$；否则本轮返回 $\mathrm{\perp }$。两种确定结论都不会错，也不可能在同一输入上冲突。

每轮耗时有多项式上界，用新随机币重试便得到 ZPP 算法。这是两种可靠输出方向的组合，不是把任意两个可能出错的答案互相投票。

反向从三输出的 ZPP 刻画出发：将 $\mathrm{\perp }$ 改为拒绝，就得到 RP 算法；将 $\mathrm{\perp }$ 改为接受，就得到 coRP 算法。两方向合起来证明

随机快速排序展示了什么 ​

以互异键的随机快速排序为例，无论选到哪些枢轴，完成时都给出正确排序。对每个固定输入，它的期望比较次数为 $O(n\log n)$，而某些枢轴序列可能产生 $\mathrm{\Theta }(n^2)$ 次比较。这展示了“答案固定正确、成本随随机性波动”的 Las Vegas 形态。

排序是函数问题，而 ZPP 的对象是语言判定问题，因此不能直接把“快速排序”当成 ZPP 中的一个语言。这个例子的作用是解释时间保证的含义，而不是证明某个困难判定问题因此属于 ZPP。

期望界与截止时间 ​

仅从 $\mathbb{E}T\le p(n)$ 可推出 $\text{Pr}(T>kp(n))\le 1/k$，不能直接宣称原算法具有指数下降的运行时间尾部。截断后独立重启则不同：连续 $k$ 轮均失败的概率至多 $2^{-k}$。指数尾来自重新安排运行方式，而非把 Markov 界的 $1/k$ 擅自改成 $2^{-k}$。

固定截止时间后强行猜一个 $0/1$ 会引入错误，因而这个被截断的程序不再满足零错误定义；保留 $\mathrm{\perp }$ 才保留可靠输出。有限次多数投票只能降低已有错误概率，不能一般性地把它变成零错误：必须存在可被可靠识别的成功条件。

确定性多项式算法是不使用随机币的特例，故P理路复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 包含于 ZPP。将三输出算法独立运行两轮，再把两轮都失败的情形任意映射为 $0/1$，错误概率至多 $1/4$，于是

把一个 ZPP 算法的最终 $0/1$ 对调，期望时间不变，因此 ZPP 对补语言封闭；这也与 $\mathrm{RP}\cap \mathrm{coRP}$ 的对称性一致。

设计此类算法时，核心任务是把不确定性变成可检测的“重试”，并对每个固定输入给出非微小的成功概率。一个永远答对却经常等待极久的过程，和一个总是很快却可能悄悄答错的过程，都尚未同时满足这两个要求。

这里约束的是随机运行时间的期望，而不是每条随机执行路径都满足同一个时间复杂度理路时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。上界。