随机与交互计算

允许算法抛掷硬币或与强大但不受信任的证明者进行对话，产生了诸如BPP和IP等复杂性类，这些复杂性类重塑了我们对高效验证所能实现目标的理解。

Definition

随机计算通过让机器访问随机比特来增强其能力，并衡量正确答案的概率；而交互计算则允许多项式时间验证者与证明者交换消息；由此产生的复杂性类捕获了可以通过有界误差解决或通过交互验证的问题。

Scope

本主题涵盖概率复杂性类，包括BPP、RP和ZPP，以及随机性是否可以消除的问题、交互式证明系统以及将IP与PSPACE等同的定理、零知识证明，以及作为近似硬度基础的可概率检查证明。

Core questions

• 访问随机性是否能让算法更有效地解决更多问题？
• 有限的验证者能否检查不受信任的强大证明者所提出的主张？
• 如何在确信某个陈述为真的同时，不获取任何其他信息？
• 交互式和概率性证明检查如何限制近似？

Key theories

IP 等于 PSPACE

通过多项式时间验证者与全能证明者之间的交互协议可证明的语言，恰好是那些可在多项式空间中判定的语言，这充分体现了交互的强大能力。

PCP 定理

NP中的每个问题都具有可以通过读取常数数量的随机选择比特来验证的证明，这一结果确定了许多优化问题近似难度达到NP-hard的精确阈值。

Clinical relevance

这些思想具有直接的技术影响：零知识证明实现了身份验证和隐私保护协议，并支撑了区块链中的可验证计算；而可概率检查证明解释了为什么许多优化问题无法被有效近似，从而指导了近似算法的适用范围。

History

交互式和零知识证明由Goldwasser、Micali和Rackoff以及Babai在20世纪80年代中期引入。Shamir于1990年证明了IP等于PSPACE，而由Arora等人在20世纪90年代早期完成的PCP定理彻底改变了近似研究，而关于随机多项式时间等于确定性多项式时间的悬而未决的猜想仍然开放。

Debates

随机性是否增加了真正的计算能力？

许多结果表明，在合理的难度假设下，BPP等于P，这意味着随机性原则上可以从高效算法中移除。这种去随机化是否无条件成立仍未解决，这使得随机性的本质重要性仍有待探讨。

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

抛掷硬币如何帮助算法？

随机性允许算法通过做出对手无法预测的选择来避免最坏情况的输入，通常会产生更简单或更快的程序，例如在素性测试中。有界误差类BPP捕获了以这种方式解决的问题，且具有可控的小错误概率。

什么是零知识证明？

它是一种交互式协议，能够使验证者确信某个陈述为真，同时除了其真实性之外不透露任何其他信息，甚至不透露其成立的原因。例如，此类证明允许您在不泄露密码或秘密的情况下证明您知道它们，并且它们是现代密码学隐私的基础。