交互式多项式时间复杂性类

交互式多项式时间复杂性类（class of interactive polynomial time，IP），计算机科学技术名词，一个复杂性类，包含如下定义的语言：给定语言 L ，如果存在一个随机化多项式时间验证者 V ，它可以和任何证明者交互次，使得对任何 x ：①如果 x∈L ，那么存在证明者 P ，使得Pr［< V， P >接受 x ］=1；②如果 xL ，那么对任何证明者 P ，Pr［< V，P >接受x]<成立，那么我们称 L 属于交互式多项式时间复杂性类，记为 L ∈IP。