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ᶜ)$ 或更快（其中 $n$ 是输入大小，$c$ 是非负常数），我们称该算法需要多项式时间。我们可能会将运行时间在多项式时间或更快的算法称为高效算法，因为它们的运行时间不会随着输入大小的增加而增长过快。

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

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

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

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

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

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

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

• 求解： 对列表进行排序需要 $\mathcal{O}(n \log n)$ 的时间（例如，使用归并排序），这属于多项式时间。虽然 $n \log n$ 不是多项式，但我们知道 $\log n < n$，因此 $(n \log n) < n²$，所以我们算法的运行时间受某个多项式的上限约束，这符合“多项式时间”的要求。

• 验证： 我们可以通过遍历列表并检查每个项是否大于其左侧相邻项来验证列表是否已排序，这需要 $\mathcal{O}(n)$ 的时间。

P 类问题示例 2：如果数字在列表中，返回其索引

我们可以高效地搜索以查看数字是否在列表中；如果我们知道其所在的索引，我们甚至可以更高效地验证该数字是否存在。

• 求解： 例如，给定列表 [8, 2, 1, 6, 7, 3]，我们需要 $\mathcal{O}(n)$ 的时间来确定数字 7 是否在列表中。

• 验证： 但是如果我们给你这个列表，并告诉你 7 在索引 4 处，你可以在 $\mathcal{O}(1)$ 的时间内验证该数字是否在列表的该位置。在一般情况下，如果没有被告知项的位置而搜索它，需要 $\mathcal{O}(n)$ 的时间，因为我们必须遍历列表进行搜索。如果我们被告知了该项的假定位置，只需 $\mathcal{O}(1)$ 的时间就能验证该项确实位于列表的该位置。

P 类问题示例 3：确定图中的两个节点是否连通

我们可以通过使用广度优先搜索高效地确定图中的两个节点是否连通——从一个节点开始，然后访问其所有未访问过的邻居节点，接着搜索邻居的邻居，依此类推。

• 求解： 使用广度优先搜索发现节点之间的路径将花费 $\mathcal{O}(n + e)$ 的时间，其中 $n$ 是图中的节点数，$e$ 是边数。边数 $e$ 不能超过 $n^2$，因此在最坏情况下，我们可以将 $\mathcal{O}(n + e)$ 视为 $\mathcal{O}(n²)$。

• 验证： 我们只需顺着给定的路径查看这两个点是否真的由该路径连通，即可在 $\mathcal{O}(n)$ 的时间内验证提议的路径是否有效。

在上述所有示例中，计算和验证解决方案都可以在多项式时间内完成。

见证

在计算机科学中，见证（witness）是你正确解决了问题的证据。在上面的示例中，见证就是问题的正确答案。对于上述示例，我们可以用作见证的包括：

1. 排序好的列表
2. 数字在列表中出现的索引
3. 图中两个节点之间的路径

我们稍后会看到，见证不一定非要是原问题的解决方案。它也可以是同一问题的另一种替代表示形式的解决方案。

PSPACE 类问题：并非所有问题都有可以被高效验证的解决方案

需要指数级资源来求解和验证的问题被称为 PSPACE 类问题。它们之所以被称为 PSPACE，是因为尽管它们可能需要指数时间来求解，但它们不一定需要指数级的内存空间来执行搜索。

这类问题已经被广泛研究，但尚未发现任何高效的算法来解决它们。许多研究人员认为根本不存在解决这些问题的高效算法。如果能发现解决这些问题的高效方法，人们甚至可能重用该算法来破解所有现代加密技术，并从根本上改变我们所认知的计算领域。

尽管寻找这些问题的高效解决方案有着巨大的诱惑，但有证据表明此类解决方案很可能不存在。这些问题非常具有挑战性，以至于即使你正确地解决了它们，你也无法提供易于验证的证据（见证）。

PSPACE 类问题示例

PSPACE 示例 1：寻找国际象棋的最佳走法

假设我们问一台功能强大的计算机：“在给定这个棋盘及其棋子位置的情况下，下一步的最佳走法是什么？”

计算机回答：“将 f4 上的黑兵移动到 f3。”

你如何能相信计算机给你的是正确答案呢？

没有高效的方法来进行检查——你必须完成与计算机相同的工作。这涉及对所有可能的未来棋盘状态进行全面搜索。计算机无法为我们提供任何见证，能让我们确认“将 f4 上的黑兵移动到 f3”确实是下一步的最佳走法。这样一来，这个问题的本质就与之前讨论的示例大不相同：我们无法高效地验证声称的最佳走法就是真正的最佳走法。

在这个例子中，计算机呈现的“见证”由所有未来潜在的对局状态组成。然而，其庞大的数据量使得实际上不可能高效地验证该解决方案的准确性。

PSPACE 示例 2：确定正则表达式（regexes）是否等效

两个正则表达式 a+ 和 aa* 匹配相同的字符串。如果一个字符串匹配第一个正则表达式，它也会匹配第二个，反之亦然。

然而，检查两个任意的正则表达式是否等效需要耗费指数级的计算时间。即使一台强大的计算机告诉你它们匹配相同的字符串，计算机也无法给你提供简短的证明（见证）来表明答案是正确的。与国际象棋的例子类似，你必须搜索一个非常庞大的字符串空间以检查正则表达式是否等效，而这将花费指数级的时间。

国际象棋和正则表达式等效性都有一个共同特征，那就是它们都需要指数级的资源来寻找答案，并且也需要指数级的资源来验证答案。

计算密集度甚至高于 PSPACE 的问题

还有些极其困难的问题，它们需要指数级的时间和指数级的内存来解决，但这些问题通常是理论上的，在现实世界中并不常出现。

此类问题的一个例子是带有“棋子永远不能移动到会重现早期棋盘状态的位置”规则的西洋跳棋。为了确保在探索可能走法的空间时不会在对局中重复棋盘状态，我们必须记录所有已经访问过的棋盘状态。由于对局长度可能随棋盘大小呈指数增长，因此其内存需求也是指数级的。

NP 类问题：有些问题可以快速验证但不能快速计算

如果我们可以快速验证一个问题的解决方案，那么该问题就属于 NP。然而，找到该解决方案可能需要指数级的资源。

任何其提议的解决方案（见证）可以被快速验证为正确的问题都是 NP 问题。如果该问题也有一个在多项式时间内寻找解决方案的算法，那么它就是一个 P 问题。所有的 P 问题都是 NP 问题，但极不可能所有的 NP 问题也都是 P 问题。

NP 类问题的例子。下面将对这些进行更详细的解释：

• 计算数独谜题的解——验证数独谜题的提议解。
• 计算地图的 3 染色（如果存在的话）——验证提议的地图 3 染色。
• 为布尔公式寻找使其结果为 true 的赋值——验证提议的赋值会导致公式结果为 true。

注意： NP 代表非确定性多项式（non-deterministic polynomial）。我们不会深入探讨这个名称由来的行话；我们只是给出这个名称，以免读者误以为它代表“非多项式时间”。

NP 类问题示例

NP 示例 1：数独

在数独游戏中，玩家会得到一个 $9 \times 9$ 的网格，其中已经填好了一些数字。玩家的目标是用 1-9 的数字填满网格的其余部分，使得任何行、列或 $3 \times 3$ 粗线方块中都不出现重复的数字。以下来自 Wikipedia 的图片说明了这一点。在第一张图片中，我们看到了提供给玩家的 9x9 网格。在第二张图片中，我们看到了玩家的解答。

给定一个数独谜题的解决方案，我们只需通过循环遍历列、行和 $3\times 3$ 子网格，就可以快速验证解决方案是否正确。见证可以在多项式时间内得到验证。

然而，计算解决方案需要大量得多的资源——有指数级数量的组合需要搜索。对于一个 $9\times 9$ 的网格，这对于计算机来说并不困难。但是，如果我们允许数独谜题任意变大：边长为 $n$，其中 $n$ 是 9 的倍数。在这种情况下，寻找解决方案的难度将随 $n$ 呈指数级增长。

NP 示例 2：地图的 3 染色

任何领域的 2D 地图都只需四种颜色即可被“染色”（见四色定理）。也就是说，我们可以为每个区域分配一种独特的颜色（四种颜色之一），使得没有相邻的区域具有相同的颜色。例如，下图（来自 Wikipedia）显示了用四种颜色染色的美国地图：粉色、绿色、黄色和红色。花点时间看一看并验证没有两个接壤的州被赋予了相同的颜色：

3 染色问题询问的是能否仅用三种颜色而不是四种颜色对地图进行染色。发现一种 3 染色（如果存在的话）是一个计算密集的搜索问题。然而，验证一个提议的 3 染色很简单：遍历每个区域，并检查没有任何相邻区域的颜色与当前正在检查的区域相同即可。

事实证明，是不可能对美国进行 3 染色的。

特定地图无法进行 3 染色的原因各不相同，但以美国为例，内华达州（下图中 红色 的区域）被五个领地包围。我们用一种颜色给内华达州染色，然后我们必须交替为其相邻领地染色。然而，当我们绕完内华达州的邻居一圈时，我们最终会得到一个领地，其边界上有三种颜色的邻居，这使得那个未着色的领地再无有效颜色可用。

如果你想了解更多关于这个问题的知识，这里有一个关于 3 染色地图的快速且有趣的视频。

然而，对澳大利亚进行 3 染色是可能的：

并非所有地图都可以 3 染色。对任意 2D 地图计算出一种 3 染色（如果存在），是无法高效完成的——它通常需要暴力搜索，可能耗费指数时间。

但是，如果有人解出了 3 染色，验证他们的解决方案是非常容易的。

P、NP 和 PSPACE 之间的关系

各个类别的计算资源

下表总结了每一类问题所需的计算资源：

P、NP 和 PSPACE 之间的难度层级

任何验证其见证需要指数级资源的问题都是 PSPACE（或更难的）问题。如果某人拥有指数级资源来验证 PSPACE 问题的见证，他就能轻而易举地计算出任何 P 或 NP 问题的解。因此，所有 P 和 NP 问题都是 PSPACE 问题的子集，如下图所示。

换句话说，如果你有一台足够强大的计算机来求解或验证较大圆圈中的一类问题，你也可以求解或验证其子集：

P 与 NP 问题

P 类是可以高效求解和验证的问题类别，而 NP 类是可以高效验证的问题类别。“P 与 NP”问题简单来说就是询问这两个类别是否相同。

如果 P = NP，这意味着只要我们能找到验证解的高效方法，我们也就一定能找到寻找该解的高效方法。请记住，寻找解决方案总是至少和验证它一样困难。（根据定义，解决一个问题包含了找到正确答案的过程，这意味着求解问题的算法在执行过程中也同时验证了它的答案）。

如果 P = NP 成立，那意味着存在计算（任意大小）数独谜题以及查找是否存在 3 染色解的高效算法。这也意味着存在破解大多数现代密码学算法的高效算法。

目前，P 和 NP 是否为同一集合仍未被证明。尽管人们已进行了无数次尝试为 NP 问题寻找高效算法，但所有证据都表明这种算法并不存在。

同样，PSPACE 问题是否存在高效求解或验证机制仍然是一个悬而未决的问题。虽然研究人员普遍推测 P ≠ NP 且 NP ≠ PSPACE，但这些结论尚无正式的数学证明。因此，尽管付出了大量努力，NP 问题的高效解法以及 PSPACE 问题的高效验证方法依然未被发现。

出于实际目的考虑，我们可以假设 P ≠ NP 且 NP ≠ PSPACE。事实上，当我们把重要数据托付给现代密码学算法时，我们已经隐式地做出了这一假设。

第二部分：将问题和解决方案表示为布尔公式

将 P 和 NP 问题联系在一起的是，它们的解决方案都可以被快速验证。如果我们能用一种通用语言来描述所有这些（P 和 NP）问题及其解决方案，那将极其有用。也就是说，我们想要一种能适用于各种不同问题的编码方式，无论是证明一个列表已排序，还是证明解出了数独谜题，亦或是证明我们有一种 3 染色方案。

对 NP 或 P 类问题的解决方案进行验证，可以通过验证一个模拟了该问题的布尔公式的解来实现。

当我们描述“布尔公式的解”是什么意思，并探讨一些用布尔公式对问题建模的示例后，我们所说的“模拟了该问题的布尔公式”的含义就会变得清晰。

布尔公式的解

为了表示布尔公式，我们使用运算符 $¬$ 表示布尔非（NOT），$∧$ 表示布尔与（AND），$∨$ 表示布尔或（OR）。例如，当且仅当 $a$ 和 $b$ 均为 true 时，$a ∧ b$ 的计算结果为 true。当且仅当 $a$ 为 true 且 $b$ 为 false 时，$a ∧ ¬b$ 的计算结果为 true。

假设我们有一组布尔变量 $x₁$、$x₂$、$x₃$、$x₄$ 以及一个布尔公式：

问题是：我们能否为 $x₁, x₂, x₃, x₄$ 找到对应的值，使得 $out$ 为 true？对于上面的公式，我们可以。用 $T$ 表示 true，$F$ 表示 false，我们可以将解写成：

将解代入公式可得：

这很容易验证，但是为一个非常庞大的布尔公式寻找解可能需要指数级的时间。为布尔公式求解本身也是一个 NP 问题——它可能需要指数级的资源来寻找解，但验证它可以在多项式时间内完成。

但我们必须强调：我们使用布尔公式的目的并非为了求解它们——只是为了验证其提议的解。

所有 P 和 NP 问题都可以通过转换为布尔公式并展示该公式的解来进行验证

在接下来的示例中，输入是一个 P 或 NP 问题，而输出是一个布尔公式。如果我们知道原问题的解，那么我们也将知道布尔公式的解。

我们的意图是证明我们知道原问题的见证——只是以布尔的形式呈现。

示例 1：使用布尔公式检查列表是否已排序

考虑 1 比特的二进制数字 $A$ 和 $B$。当 $A > B$ 时，以下真值表返回 true：

$A > B$ 列可以用表达式 $A ∧ ¬B$ 建模，它会在仅有的 $A > B$ 为 1 的行中返回 true。

现在考虑一个表示 $A = B$ 的表：

$A = B$ 列可以用表达式 $(A ∧ B) ∨ ¬(A ∨ B)$ 建模。当 $A = 1$ 且 $B = 1$ 时，$(A ∧ B)$ 返回 true；当 $A$ 和 $B$ 均为零时，$¬(A ∨ B)$ 返回 true。

对 1 比特数字的表达式：

很快就会派上用场。

那么，我们要如何比较多于 1 个比特的二进制数字呢？

根据最高有效不同位进行二进制比较

假设你从这两个数字最左侧的最高有效位（MSB）开始，向右移向最低有效位（LSB）。在两个数字出现差异的第一个比特位处：

如果 $P$ 在该位上的值为 $1$ 而 $Q$ 的值为 $0$，那么 $P ≥ Q$。
下面的动画演示了算法检测到 $P ≥ Q$ 的过程：

如果 $P = Q$，则所有位均相等。$P = Q$ 意味着 $P ≥ Q$ 也为真：

如果 P < Q，那么我们将在出现 Q 为 1 且 P 为 0 的第一个位处检测到这一点：

不失一般性，假设我们将 $P$ 中的位编号为 $p₄, p₃, p₂, p₁$，并将 $Q$ 中的位编号为 $q₄, q₃, q₂, q₁$。

如果 $P ≥ Q$，那么以下其中一项必定为真：

• $p₄ > q₄$
• $p₄ = q₄$ and $p₃ > q₃$
• $p₄ = q₄$ and $p₃ = q₃$ and $p₂ > q₂$
• $p₄ = q₄$ and $p₃ = q₃$ and $p₂ = q₂$ and $(p₁ > q₁ \text{ or } p₁ = q₁)$

我们可以将这些条目组合成一个方程式。

回想一下我们用来对 1 比特等量和比较进行建模的布尔表达式：

我们可以将 $A > B$ 和 $A = B$ 的公式代入上面的等式中。为了避免满篇都是数学公式，我们在下方以视频形式展示运算过程：

对于 4 个比特，表达 $P ≥ Q$ 的最终布尔公式为：

我们将以如上所述的方式比较两个二进制数字的布尔表达式称为“比较表达式”。

检查列表是否已排序

给定一个比较固定大小数字的布尔公式，我们可以重复地将该比较表达式应用于列表中的每一对相邻元素，并使用 AND（与）操作将这些比较表达式组合起来。当且仅当所有比较表达式的 AND 结果为 true 时，列表才是排好序的。

因此，我们看到证明列表已排序的见证不一定非要是排序后的列表。它也可以是我们上面创建的布尔公式的输入（只要该输入能使该公式返回 true）。

示例 2：作为布尔公式的 3 染色

让我们再次看看澳大利亚的地图：

为了将解决方案建模为布尔公式，该公式需要编码以下事实：

• 每个领地具有三种颜色之一
• 每个领地具有与其邻居不同的颜色

例如，要表示西澳大利亚是绿色、蓝色或红色，我们需要创建三个变量 WESTERN_AUSTRALIA_GREEN、WESTERN_AUSTRALIA_BLUE、WESTERN_AUSTRALIA_RED。为了避免变量名过长，我们将其称为 WA_G、WA_B 和 WA_R。此时我们的布尔公式为：

Copy
(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

换句话说：

"（西澳大利亚是绿色 且 西澳大利亚不是蓝色 且 西澳大利亚不是红色）

或者

（西澳大利亚不是绿色 且 西澳大利亚是蓝色 且 西澳大利亚不是红色）

或者

（西澳大利亚不是绿色 且 西澳大利亚不是蓝色 且 西澳大利亚是红色）"

为布尔公式添加颜色以示强调：

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

我们将上面的公式称为颜色分配约束。

我们使用布尔变量来编码领地被分配的颜色。由于布尔变量只能包含两个值，而一个领地可以是三种颜色之一，因此每个领地被分配三个布尔变量，每种颜色一个。如果一个领地被分配了特定的颜色，则相应的变量设置为 true，而其他的设置为 false。

当且仅当西澳大利亚的领地被精确分配了一种颜色时，上面的公式才为 true。

相邻颜色约束

接下来，我们要写一个公式，表示 WA 具有与其邻居不同的颜色。我们像为 WA 做的那样，为 SA（南澳大利亚）创建三个变量。现在，我们的公式简单地表示，“对于每种颜色，WA 和 SA 不会同时是那种颜色”。这等同于说“WA 和 SA 的颜色不相同”。我们使用变量名 SA_G、SA_B 和 SA_R 来指代南澳大利亚（毗邻西澳大利亚）的颜色分配。我们使用下面的公式来表示它们具有不同的颜色：

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

换句话说：

以下情况不成立：（西澳大利亚是绿色 且 南澳大利亚是绿色）

且

以下情况不成立：（西澳大利亚是蓝色 且 南澳大利亚是蓝色）

且

以下情况不成立：（西澳大利亚是红色 且 南澳大利亚是红色）"

当且仅当西澳大利亚和南澳大利亚未被分配相同颜色时，上述公式才能被满足。我们将上述公式称为边界约束。

我们需要对每个领地应用颜色分配约束，对每一对邻居应用不同颜色约束，然后用 AND 将所有约束组合在一起。

为澳大利亚 3 染色建模的公式

我们现在展示验证澳大利亚有效 3 染色的最终布尔公式。以下是标记的领地：

首先，我们为每个领地分配一个变量名：

• WA = 西澳大利亚 (West Australia)
• SA = 南澳大利亚 (South Australia)
• NT = 北领地 (Northern Territory)
• Q = 昆士兰 (Queensland)
• NSW = 新南威尔士 (New South Wales)
• V = 维多利亚 (Victoria)

颜色约束：六个领地中每一个都恰好有一只颜色：

边界约束：每个相邻领地的颜色互不相同

接下来，我们遍历边界并计算那些邻居的边界约束。下面的视频展示了算法的作用过程。在视频下方，我们展示了用于边界条件的最终公式集：

7. 西澳大利亚 和 南澳大利亚：

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

8. 西澳大利亚 和 北领地：

¬(WA_G ∧ NT_G) ∧ ¬(WA_B ∧ NT_B) ∧ ¬(WA_R ∧ NT_R)

9. 北领地 和 南澳大利亚：

¬(NT_G ∧ SA_G) ∧ ¬(NT_B ∧ SA_B) ∧ ¬(NT_R ∧ SA_R)

10. 北领地 和 昆士兰：

¬(NT_G ∧ Q_G) ∧ ¬(NT_B ∧ Q_B) ∧ ¬(NT_R ∧ Q_R)

11. 南澳大利亚 和 昆士兰：

¬(SA_G ∧ Q_G) ∧ ¬(SA_B ∧ Q_B) ∧ ¬(SA_R ∧ Q_R)

12. 南澳大利亚 和 新南威尔士：

¬(SA_G ∧ NSW_G) ∧ ¬(SA_B ∧ NSW_B) ∧ ¬(SA_R ∧ NSW_R)

13. 南澳大利亚 和 维多利亚：

¬(SA_G ∧ V_G) ∧ ¬(SA_B ∧ V_B) ∧ ¬(SA_R ∧ V_R)

14. 昆士兰 和 新南威尔士：

¬(Q_G ∧ NSW_G) ∧ ¬(Q_B ∧ NSW_B) ∧ ¬(Q_R ∧ NSW_R)

15. 新南威尔士 和 维多利亚：

¬(NSW_G ∧ V_G) ∧ ¬(NSW_B ∧ V_B) ∧ ¬(NSW_R ∧ V_R)

我们对上面提到的 15 个公式执行布尔与（AND）操作，从而创建一个布尔公式。拥有一个使布尔表达式结果为 true 的变量赋值，相当于拥有一种针对澳大利亚的有效 3 染色方案。

换言之，如果我们知道针对澳大利亚的有效 3 染色方案，那么我们也知道在上面构建的布尔公式的一个赋值。

布尔公式必须能在多项式时间内构建

我们只需要花费多项式数量的步骤，即可为 3 染色构建出这个布尔公式。具体来说，我们需要：

• 每个领地 3 个颜色约束
• 每个领地最多 N 个相邻颜色约束

必须要求构建布尔公式所采取的步骤在多项式时间内完成。如果它需要指数级的步骤，那么该布尔公式将会是指数级庞大的，并且见证也将是指数级庞大的——且无法在多项式时间内验证。

使用布尔表达式建模问题及提议解决方案总结

P 和 NP 中的所有问题都可以被表示为一个布尔公式。如果我们知道对应的变量赋值（见证）（该赋值编码了原问题的一个正确解），那么这个布尔公式就会输出 true。

现在我们拥有了一种标准语言来高效证明某个问题的解决方案，我们就离实现“证明我们拥有一个问题的解而不泄露该解”（即零知识证明）的标准方法更近了一步。

第三部分：P 与 NP 及 ZK 证明

P = NP 与 ZK 证明之间的关联

零知识证明中的“知识”指的是对见证的知识。

ZK 证明关注的是计算中的验证环节。也就是说，鉴于你已经找到了一个数独的解或者地图的 3 染色方案，你能不能向某人提供证据（见证），使得他们能够高效地验证你的解是正确的？

ZK 证明力求展示你知道该见证，而不将见证内容暴露出来。

ZKP 仅适用于 P 或 NP 问题。它们不适用于我们无法高效验证的问题。

如果我们没有一种机制来高效证明正则表达式是等效的，或者证明国际象棋中的特定一步是最佳走法，那么 ZK 证明也不可能奇迹般地让我们产生这样的高效证明。

对于 P 和 NP 问题来说，其解决方案的验证都可以高效地完成。ZK 支持在验证解决方案有效性的同时隐藏计算细节。此外，ZK 无法帮助你发掘出数独难题的解或地图的 3 染色方案。但是，如果你已经计算出了解决方案，它可以帮助你向另一方证明你拥有它。

P 与 NP 和零知识证明之间的联系

所有其解可以被快速验证的问题，都能被转换为布尔公式。

能够将任何问题转换为布尔公式并不是一种寻找答案的高效作弊码。解任意的布尔表达式本身也是一个 NP 问题，为其寻找解可能会非常困难。

布尔公式的大小至关重要。回到我们国际象棋的例子中，如果你尝试用布尔公式对每个状态进行建模，那么你的公式大小将会呈指数级膨胀。因此，唯一可行的问题是 NP 或 P 类问题，因为它们拥有可以对其建模且大小合理的布尔公式。

在 ZK 领域的文献中，我们通常将布尔公式称为布尔电路。

为一个问题创建零知识证明，归根结底就是将该问题转换为电路，正如在证明澳大利亚的 3 染色或验证排序列表时所演示的那样。然后，你证明你拥有该电路的有效输入（即见证），最终这就转化为了零知识证明。

高效验证问题解决方案的能力，是创建表明你拥有该解决方案的零知识证明的一个先决条件。人们必须能够构建布尔电路来高效模拟该解决方案。然而，对于决定国际象棋最佳走法这样属于 PSPACE 类的问题，这种方法会导致极其庞大的指数级电路，因而是不切实际的。

总之，零知识证明仅适用于 P 和 NP 类别之内可以被高效验证其解决方案的问题。如果缺乏高效的验证机制，为一个问题创建零知识证明就变得不可行了。

了解更多

有关零知识证明的更多主题，请参阅 RareSkills ZK Book。

技术细节

本文对某些概念进行了简化，以使初次接触它们的人能够尽可能通俗易懂地理解。此处提供的信息足以解释 ZK 证明能做什么以及不能做什么。对于有兴趣深入探讨该主题的人，以下是一些说明：

• 一个固定大小 $(8 \times 8)$ 的国际象棋棋盘无法被赋予难度级别，因为问题的难度无法表示为 $\mathcal{O}(f(n))$。严格来说，我们说任意大小的国际象棋属于 PSPACE。想象一个 $10 \times 10$ 的棋盘可能会让人困惑，但其实只需指定额外的空间在起始位置没有任何棋子即可。

• 国际象棋有一条不太为人所知的规则，即如果在过去 50 步中没有任何吃子动作且没有兵移动，那么玩家可以提出和棋。这为搜索空间设定了一个界限，使其归为 PSPACE 问题。如果取消此规则，那么该版本的国际象棋属于 EXPSPACE——一类需要指数时间与指数内存大小进行计算的问题。

• 一些 NP 问题可以在次指数时间内求解，但从实际应用的角度来看，解决它们需要指数级的时间。例如 $\mathcal{O}(2^{\sqrt{n}})$ 在严格意义上是次指数级的，但它依然具有指数级的难度。

• 为某些 NP 问题寻找解决方案的非常强大的启发式算法已经存在。虽然 3 染色求解需要指数时间，但许多大小适中的问题实例仍能被快速解决。例如，这里有 200 个领地的有效 3 染色地图基准问题。巧妙的算法能够在不需要探索指数级庞大搜索空间的情况下找出解。然而，对于任何旨在加速求解 NP 问题的启发式算法，总是可能刻意制造一种极端的问题实例，专门针对并利用该启发式算法，使其变得毫无价值。尽管如此，在应对该问题的典型现实例子时，启发式算法依然非常有效。

最初发布于 2024 年 4 月 10 日