【摘要】很多随机算法并不是靠“运气好”工作，而是靠候选空间里存在大量可用证据。只要证据足够密集，随机抽样就不再像碰运气，而更像一种低成本的搜索策略。 对于某个输入 \(x\)，如果额外给出一段信息 \(w\)，我们就能比直接求解更高效地验证某个结论。在计算复杂性中，这类辅助信息通常被称为 witness，也 阅读全文