交互式证明系统

在计算复杂性理论中，交互式证明体系（下简称交互证明）是一类计算模型。在计算复杂性理论中，像其它计算模型一样，我们的目标是对一个语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。