第八章 交互式证明
什么是一个好的证明系统天生必须具备的性质？
-
所有正确的能被证明；
-
所有错误的不能被证明；
-
证明者的证明过程和计算量可以很大，但是验证者所需的工作量不应该太大。
—— Goldwasser, Micali, Rackoff 1985
什么是交互式证明？可以先假定它指的是一个证明系统，其中存在证明者和验证者。验证者提问，证明者回答，验证者通过其回答确定是否接受证明者给出的证明的正确性。
8.1 基于确定性验证者的交互式证明
不妨假设双方都可以保存一个当前状态，即双方
Def.（确定性函数的交互）
标签：计算,验证,复杂性,第八章,证明,交互式 From： https://www.cnblogs.com/hokarikanae/p/18041618