形式陈述

对语言 $L$，交互证明由概率多项式时间验证者 $V$ 与证明者 $P$ 的消息协议组成。 完整性要求 $x\in L$ 时存在证明者策略使 $V$ 以高概率接受；可靠性要求 $x\notin L$ 时任意证明者策略的接受概率都低。 误差常数可通过独立重复降低。复杂性类 IP 收集拥有此类协议的语言。

直觉

证明不再是一份静态字符串；验证者用随机挑战迫使证明者持续给出彼此一致的局部回答。

例子与边界

图同构补图协议展示随机挑战的力量。交互证明本身不保证零知识，也不自动是 argument：若可靠性只针对高效作弊者，模型才转为计算可靠的论证系统。

推论与应用

它是零知识、Sigma 协议、概率可检验证明和 IP=PSPACE 的基础对象。

参考资料

• Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach (2009), interactive proofs.
• Shafi Goldwasser, Silvio Micali, Charles Rackoff, The Knowledge Complexity of Interactive Proof Systems (1989), interactive proofs and knowledge complexity.