交互式证明系统 在计算复杂性理论中交互式证明体系下简称交互证明是一类计算模型像其它计算模型一样交互证明的目标是对一个语言L和一个给定的输入x判断x是否在L中交互证明由两个实体验证者verifier和证明者prover组成两者都可以看作是某类图灵机而它的计算过程为给定了输入x通过验证者和证明者之间交换信息最终由验证者来根据证明者给出的信息判断给定的输入是不是在语言L中 交互证明的基本假设是证明者在计算能力上是无限的在概率多项式时间BPP 複雜度的图灵机一般来说对给定的L我们关注的是交互证明中验证者V这一角色并对它加以如下的要求 完备性completeness如果xL那么存在诚实的证明者P使得V与P的交互之后输出xL 可靠性soundness如果xL那么对任意的证明者PV与P交互之后输出xL的概率很小可以认为小于某一常数 如果对L这样的验证者存在那么称L有这样的一个交互体系 类似对图灵机所需的运行时间和空间等加以限制来得到语言的集合复杂性类一样通过改变交互证明中交互过程的轮数随机源是公开的还是验证者所私有的以及证明者的数目等等参数可以得到不同能力的证明体系并依据一个语言是不是有这样参数的交互证明来定义相应的语言的集合复杂性类依据交互证明定义的主要复杂性类有IP和AM它们与依据图灵机定义的经典复杂性类的关系是重要的研究课题