交互式证明系统

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