P = NP 问题提出了这样一个疑问：“如果我们可以快速验证一个问题的解决方案是否正确，我们是否也能快速计算出该解决方案？”大多数研究人员认为答案是否定的，即 P ≠ NP。

通过理解 P 与 NP 问题，我们可以看到零知识证明（Zero Knowledge Proofs, ZKPs）如何融入更广泛的计算机科学领域，并理解 ZKP 能做什么以及不能做什么。

将零知识证明与 P 与 NP 问题联系起来，会让我们更容易“理解”它。

本教程分为三个部分：

  1. 解释 P 与 NP 问题
  2. 将问题和解决方案表示为布尔公式
  3. P 与 NP 问题及其与零知识证明的关系

先决条件

我们假设读者熟悉时间复杂度和大 $\mathcal{O}$ 记号。

如果一个算法的运行时间为 $\mathcal{O}(n^{c})$ 或更快（其中 $n$ 是输入大小， $c$ 是非负常数），我们称该算法需要多项式时间。我们可能会将运行时间在多项式时间或更快的算法称为 高效算法 ，因为它们的运行时间不会随着输入大小的增加而增长过快。

<aside> 💡 💡 一句话理解：多项式时间就是『办得起的快』。$\mathcal{O}(n^{c})$ 里 $n$ 是数据量、$c$ 是个固定的小数字（比如 2）。打个比方：数据翻 10 倍，$n^2$ 的活儿只多 100 倍，咬咬牙还能干完。关键是这个指数 $c$ 永远钉死不动，不会随数据变大而失控。

</aside>

如果一个算法的运行时间为 $\mathcal{O}(c^{n})$ （其中 $c$ 是大于 1 的常数， $n$ 是输入大小），我们称该算法需要 指数时间 或 代价高昂 ，因为随着输入大小的增加，该算法会变得呈指数级缓慢。

<aside> 💡 💡 这里最要命的对比：指数时间 $\mathcal{O}(c^{n})$ 是把 $n$ 搬到了指数上当『楼层』。$2^{n}$ 意味着数据每多 1 个，工作量就翻一倍——$n=10$ 才 1024，$n=60$ 就超过全宇宙原子数。所以多项式 = 凡人能算完，指数 = 等到天荒地老也算不完。

</aside>

第一部分：解释 P 与 NP 问题

P 类问题既易于求解，又易于验证解决方案。

可以在多项式时间内求解，并且其解决方案可以在多项式时间内验证的问题称为 P 类问题。

下面是一些易于计算和验证解决方案的示例问题。这些任务可能会由不同的一方执行，一方进行计算，另一方检查结果是否有效：

P 类问题示例 1：对列表进行排序

我们可以高效地对列表进行排序，并且也可以高效地验证列表是否已排序。