48.交互式证明系统

title: 48. 交互式证明系统 tags: zk computation theory interactive proof system IP WTF zk 教程第 48 讲：交互式证明系统 这一讲，我们将介绍交互式证明系统，探讨证明系统、空间复杂性、IP 复杂性类等概念。最早的零知识证明系统是交互式证明系统，理解这些概念非常重要。 空间复杂性 在讨论交互式证明系统之前，我们需要简单了解空间复杂性和 PSPACE 复杂类，这对于之后理解 IP = PSPACE 很有帮助。 1.1 空间复杂性 时间复杂性类似，空间复杂性关注的是算法在解决问题时所需的存储空间。我们通常用大O表示法来描述空间复杂性： 如果一个算法的空间复杂性是 $O(n)$，意味着它所需的存储空间随输入大小 $n$ 线性增长。 对于一些问题，我们可能更关心空间使用而不是时间，特别是在存储资源有限的情况下。 1.2 PSPACE 复杂类 PSPACE（Polynomial Space）包含了所有可以在多项式空间内解决的问题。PSPACE 包含了许多复杂性类，包括 P、NP、BPP 等。 形式化定义：一个语言 $L$ 属...