交互式证明系统

在计算复杂性理论中，交互式证明体系是一类计算模型。像其它计算模型一样，我们的目标是对一个语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者和证明者组成，两者都可以看作是某类图灵机。