Computational Complexity: P, NP, PPAD and Game Theory

Posted Jun 20, 2026 Updated Jun 21, 2026

By Yue Lin 260 min read

本文由 Claude Code 生成（联网检索文献后整理）。讲清算法复杂度的常用类（P、NP、co-NP、PSPACE、#P、以及 TFNP 一家的 PPAD、PLS、CLS 等）、常见归约，以及常见结论，尤其是博弈论与信息设计（含 Bayesian persuasion）相关的难度结果。仅供学习。

算法复杂度回答的不是”这个问题怎么解”,而是”这个问题到底有多难、难在哪里”。本文从最基础的 P 与 NP 讲起,经由归约这把”丈量难度的尺子”,一路走到博弈论与信息设计里那些既深刻又实用的复杂度结论:为什么算 Nash 均衡是 PPAD-complete、为什么相关均衡却能高效求出、Bayesian persuasion 又难在何处。

需要先说清楚的是:本文谈的”难度”始终是计算难度(computational difficulty),而不是”概念上是否难懂”或”工程上是否难写”。一个判定问题的难度,被定义为”任何算法在最坏情形下、随输入规模增长所必须付出的资源量级”——它是问题本身的属性,与具体某个人是否聪明、某段代码是否精巧无关。本节就来把这套度量难度的语言一砖一瓦地立起来。

复杂度在量什么:从判定问题到 P 与 NP

在谈论”某个问题难不难”之前,我们必须先把”难”这个词变成一个可以做数学的对象。复杂度理论(complexity theory)这门学问的第一步,恰恰不是去解任何具体问题,而是约定一套度量难度的语言。这一节就来打这个地基:把问题统一成判定问题,把成本统一成最坏情形下的渐近时间,然后在这套尺度上定义出 P、NP、co-NP 这几个最基本的复杂度类,并澄清一个流传极广的误解。

为什么把问题写成”判定问题”

一个判定问题(decision problem)是指答案只有”是 / 否”两种的问题。比如”这张图里存不存在一条经过每个顶点恰好一次的回路?”“这个布尔公式有没有一组让它为真的赋值?”它们的输出都是一个比特。这看起来像是自缚手脚,因为我们平时真正想要的往往是”找出那条回路”“给出那组赋值”,这类搜索问题(search problem)或优化问题(optimization problem)显然信息量更大。

之所以仍然以判定问题为基本对象,有几个理由。第一,判定问题在形式上最干净:一个判定问题可以等同于一个语言(language),也就是所有”是”实例的编码构成的字符串集合,于是”求解一个问题”就等价于”判断一个字符串是否属于某个集合”,可以直接架在图灵机(Turing machine)这套严格模型上,不必为每类问题单独设计度量。说得更精确一些:固定一个有限字母表 $\Sigma$(常取 $\Sigma={0,1}$),把每个实例都编码成一个有限字符串 $x\in\Sigma^$($\Sigma^$ 指 $\Sigma$ 上所有有限字符串的集合);一个语言就是一个子集 $L\subseteq\Sigma^*$。判定问题”$x$ 是不是’是’实例”就等价于”$x\in L$ 是否成立”。例如”图中是否存在哈密顿回路”这个问题,对应的语言就是

\[L_{\mathrm{HAM}}=\{\,\langle G\rangle : \text{图 } G \text{ 含一条哈密顿回路}\,\},\]

其中 $\langle G\rangle$ 表示图 $G$ 的某种固定编码(例如邻接矩阵按行拼成的 0/1 串)。注意编码方式不影响难度的本质:任意两种”合理”编码之间可以多项式时间互转,所以只要约定一种即可。

补充:什么是图灵机(Turing machine)

既然 P、NP 这些类都是用”在图灵机上多项式时间可解”来定义的,这里有必要把图灵机本身讲清楚。图灵机是 Alan Turing 在 1936 年提出的、用来精确刻画”机械计算”的数学模型,你可以把它想成一台理想化到极致的简陋计算机:它简单到能用纸笔分析,却强大到足以表达一切”算法”做得到的事。

一台图灵机可以严格地写成一个七元组 $(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{acc}},q_{\text{rej}})$,下面逐个说明它的零件。

纸带(tape):一条向右无限延伸、被划成一格格的纸带,它同时充当输入、草稿纸与输出。每一格里恰好写着纸带字母表 $\Gamma$ 中的一个符号;$\Gamma$ 是有限集合,含一个特殊的空白符 $\sqcup$ 以及输入字母表 $\Sigma$。开始时,长度有限的输入从最左端依次写在纸带上,其余各格全为空白符。
读写头(head):任一时刻只停在某一格上。它先读出该格符号,然后在一步之内完成三件事:往该格写入一个符号(可与原符号相同)、向左或右移动恰好一格、并切换到一个新状态。
状态(state):一个有限的控制状态集合 $Q$,机器在任一时刻恰好处于其中一个状态,可理解为”程序此刻执行到哪一行”。$Q$ 中有三个特殊状态:唯一的起始状态 $q_0$,以及两个停机状态,即接受状态 $q_{\text{acc}}$ 与拒绝状态 $q_{\text{rej}}$;一旦进入这两者之一,机器立即停止。
转移函数(transition function) $\delta$:这就是机器写死的”程序”,一张查找表,形式上是

\[\delta:\ \bigl(Q\setminus\{q_{\text{acc}},q_{\text{rej}}\}\bigr)\times\Gamma\ \longrightarrow\ Q\times\Gamma\times\{L,R\}.\]

读法是:给定”当前状态”与”读写头下方的符号”这一对输入,$\delta$ 唯一地返回一个三元组:要切换到的新状态、要在本格写下的符号、以及移动方向(左 $L$ 或右 $R$)。这里”唯一地”是关键:每一对输入只对应一个动作,机器没有任何选择余地,这正是确定性(deterministic)的含义。

把”当前状态加整条纸带的内容加读写头的位置”合起来,称为一个格局(configuration),也就是机器某一瞬间的完整快照。计算从起始格局(状态 $q_0$、输入写在纸带上、读写头停在最左格)出发,每一步用 $\delta$ 算出下一个格局,如此一步步推进,直到进入 $q_{\text{acc}}$ 或 $q_{\text{rej}}$ 而停机。对一个判定问题(语言)而言,如果一台图灵机对每个”是”实例都停机并接受、对每个”否”实例都停机并拒绝,就说它判定(decide)了这个语言。机器一共跑了多少步,就是它在该输入上花的时间;用到了纸带上多少格,就是空间。把时间写成输入长度的函数,就得到前面说的时间复杂度,而 P、NP 等类正是据此定义的。

这里要把确定性图灵机与它的孪生兄弟讲清楚,因为这正是后文 NP 的伏笔。在确定性图灵机里,转移函数 $\delta$ 把每一对”(状态, 符号)”映到唯一一个动作,于是从起始格局出发的计算路径是一条确定的链:格局 $C_0\to C_1\to C_2\to\cdots$,结局(接受/拒绝/不停机)由输入完全决定。如果我们把转移规则从”函数”放宽成”关系”,允许每一对输入对应一个集合的可能动作:

\[\delta:\ \bigl(Q\setminus\{q_{\text{acc}},q_{\text{rej}}\}\bigr)\times\Gamma\ \longrightarrow\ \mathcal{P}\bigl(Q\times\Gamma\times\{L,R\}\bigr),\]

($\mathcal{P}(\cdot)$ 表示幂集,即”所有可能动作的集合”)那么机器在每一步就可以同时分叉,尝试多个动作。这样得到的就是非确定性图灵机(nondeterministic Turing machine)。它的计算不再是一条链,而是一棵计算树:根是起始格局,每个结点按 $\delta$ 给出的若干动作分出若干子结点。它的接受规则是”存在性”的:只要这棵树上存在一条从根到接受状态的分支,就算整台机器接受该输入;只有当所有分支都拒绝时才算拒绝。

要强调的是,非确定性图灵机并不是一台能真正造出来的机器,它是一个数学建模工具,用来精确表达”猜一个证据,再验证它”这种计算模式:每一次分叉相当于”猜一个比特”,而”存在一条接受分支”恰好对应”存在一份能通过验证的证据”。后文 NP 的定义,无论是”非确定性多项式时间可判定”,还是更直观的”答案为’是’时存在一个可在多项式时间内验证的简短证书”,讲的都是同一台机器、同一件事。确定性与非确定性之间到底差多少——也就是 P 与 NP 是否相等——正是整个领域最著名的未决问题。

为什么要用这么简陋的模型?因为它稳健:给图灵机加几条纸带、加随机存取、或换成别的任何合理计算模型,彼此之间互相模拟最多只差一个多项式因子,所以”是不是多项式时间”这件事在所有这些模型下都一致。这正是邱奇-图灵论题(Church–Turing thesis)的精神:凡是”能行可计算”的,都能由图灵机算出来。第二,判定版本与搜索版本在难度上通常是绑在一起的:如果你能高效判定”是否存在哈密顿回路”,一般也能借助它高效地把回路真的找出来(对这些问题做所谓的自归约 self-reduction)。所以把难度刻画在判定层面,并不会丢掉我们关心的本质难度。第三,判定问题让”难度的下界”有意义:要说一个问题”至少有多难”,我们需要一个边界清晰、便于互相比较的对象,而判定问题(decision problem)恰好提供了这种边界。

为什么用”最坏情形”

定了对象,还要定成本。复杂度理论度量的是一个算法在输入规模 $n$ 之下所需的资源(主要是时间,其次是空间),并且采用两个关键约定:最坏情形(worst-case)与渐近(asymptotic)。这两个约定是正交的——前者回答”在同样大小的输入里,我们盯着哪一个看”,后者回答”我们以多粗的颗粒度去看增长”;它们各自独立,可以任意组合,后面会专门提醒不要把两者混为一谈。

最坏情形意味着我们关心的是”在所有规模为 $n$ 的输入里,最费时的那一个要花多久”,而不是平均要花多久。把算法在输入 $x$ 上的运行步数记作 $T(x)$,那么最坏情形运行时间就是

\[T_{\text{worst}}(n)=\max_{|x|=n} T(x),\]

也就是对所有长度为 $n$ 的输入取最大值(对固定的 $n$,长度为 $n$ 的输入只有有限多个,所以这里确实是取最大值,而非需要无限过程的上确界)。这是一种保守的、给保证的姿态:它刻画的是算法在最不利输入下仍能兑现的承诺,因此一个最坏情形高效的算法,在任何输入上都(在渐近多项式的意义上)高效。(平均情形 $T_{\text{avg}}(n)=\mathbb{E}_{

=n}[T(x)]$ 与具体输入分布相关,是另一套更精细、也更脆弱的理论——快速排序的最坏情形是 $\Theta(n^2)$,而在随机输入下平均只有 $\Theta(n\log n)$,这种落差正说明两套度量并不等价——这里先不展开。)

渐近记号:O、Ω、Θ、o、ω 五件套

渐近意味着我们只看 $n\to\infty$ 时增长速度的量级,忽略常数因子和低阶项。这样做有深刻的理由:常数因子高度依赖于机器型号、编程语言、编译器实现等无关本质的细节,而我们想捕捉的是问题与算法内在的难度结构。把这种”只比增长量级”的思想形式化,需要一整套记号——大 O 只是其中最常用的一个。下面把五个标准渐近记号系统地讲清楚。约定 $f,g$ 都是从正整数到非负实数的函数,并设 $g$ 最终为正(即存在 $n_0$ 使 $n\ge n_0$ 时 $g(n)>0$),以免出现除以零的麻烦。

每个记号都可以从三个角度理解:用 $\exists\,c,n_0$ 的”常数封顶”定义、用极限刻画、以及与实数序关系 $\le,\ge,=,<,>$ 的类比。

大 O(big-O,$O$),对应”$\le$”。定义:$f\in O(g)$ 当且仅当 $\exists\,c>0,\ \exists\,n_0,\ \forall\,n\ge n_0:\quad f(n)\le c\,g(n).$ 直觉是”$f$ 的增长不快于 $g$,至多差一个常数倍”。极限刻画:$\limsup_{n\to\infty} f(n)/g(n)<\infty$(上极限有限即可,不要求极限存在)。它给出的是上界。我们说上界 $g$ 是紧的(tight),如果同时还有 $f\in\Omega(g)$(下界定义见下条),即 $g$ 不仅压得住 $f$、也没有高估 $f$ 的量级。
大 Ω(big-Omega,$\Omega$),对应”$\ge$”。定义:$f\in\Omega(g)$ 当且仅当 $\exists\,c>0,\ \exists\,n_0,\ \forall\,n\ge n_0:\quad f(n)\ge c\,g(n).$ 直觉是”$f$ 的增长不慢于 $g$”。极限刻画:$\liminf_{n\to\infty} f(n)/g(n)>0$。它给出的是下界。显然 $f\in\Omega(g)\iff g\in O(f)$,即上界与下界互为对偶。
大 Θ(big-Theta,$\Theta$),对应”$=$”。定义:$f\in\Theta(g)$ 当且仅当 $f\in O(g)$ 且 $f\in\Omega(g)$,等价地 $\exists\,c_1,c_2>0,\ \exists\,n_0,\ \forall\,n\ge n_0:\quad c_1\,g(n)\le f(n)\le c_2\,g(n).$ 直觉是”$f$ 与 $g$ 增长同阶“,被上下两个常数倍夹住。极限刻画:$0<\liminf f/g\le\limsup f/g<\infty$;若极限存在,则等价于 $\lim_{n\to\infty} f(n)/g(n)$ 是一个正的有限常数。$\Theta$ 是我们说”这个算法的复杂度就是 $n^2$”时心里真正想表达的那种紧界(tight bound)——它把上下界一并锁死。
小 o(little-o,$o$),对应”$<$”。定义:$f\in o(g)$ 当且仅当 $\forall\,c>0,\ \exists\,n_0,\ \forall\,n\ge n_0:\quad f(n)< c\,g(n).$ 注意这里量词从大 O 的”$\exists\,c$”变成了”$\forall\,c$”:无论常数 $c$ 取得多小,$f$ 最终都被 $c\,g$ 压住。直觉是”$f$ 被 $g$ 严格压制,在量级上可忽略”。极限刻画最干净:$\lim_{n\to\infty} f(n)/g(n)=0$。
小 ω(little-omega,$\omega$),对应”$>$”。定义:$f\in\omega(g)$ 当且仅当 $\forall\,c>0,\ \exists\,n_0,\ \forall\,n\ge n_0:\quad f(n)> c\,g(n).$ 直觉是”$f$ 严格超过 $g$,在量级上把 $g$ 甩开”。极限刻画:$\lim_{n\to\infty} f(n)/g(n)=\infty$。同样有对偶 $f\in\omega(g)\iff g\in o(f)$。

把这五者并排放在一张表里,与实数序关系的类比一目了然(下表中所有极限刻画均沿用本小节约定:$f,g$ 为正整数到非负实数的函数,且 $g$ 最终为正,从而 $f/g$ 最终有定义):

渐近记号	序类比	$\exists/\forall\,c$ 定义(最终成立)	极限刻画	含义
$f\in O(g)$	$f\le g$	$\exists c>0:\ f(n)\le c\,g(n)$	$\limsup f/g<\infty$	$f$ 增长不快于 $g$(上界)
$f\in\Omega(g)$	$f\ge g$	$\exists c>0:\ f(n)\ge c\,g(n)$	$\liminf f/g>0$	$f$ 增长不慢于 $g$(下界)
$f\in\Theta(g)$	$f= g$	$\exists c_1,c_2>0:\ c_1g\le f\le c_2g$	$0<\liminf,\ \limsup<\infty$	同阶(紧界)
$f\in o(g)$	$f< g$	$\forall c>0:\ f(n)< c\,g(n)$	$\lim f/g=0$	$f$ 严格低阶,可忽略
$f\in\omega(g)$	$f> g$	$\forall c>0:\ f(n)> c\,g(n)$	$\lim f/g=\infty$	$f$ 严格高阶

拿一个具体函数感受一下。设 $f(n)=5n^2+100n$,它和几个标尺的关系分别是:

关于 $n^2$:$\lim_{n\to\infty}\frac{5n^2+100n}{n^2}=5$,是一个正的有限常数,所以 $f\in\Theta(n^2)$——这才是它真正的量级。当然由 $\Theta$ 的定义同时有 $f\in O(n^2)$ 和 $f\in\Omega(n^2)$。
关于 $n^3$:$\lim\frac{5n^2+100n}{n^3}=0$,所以 $f\in o(n^3)$,当然也就 $f\in O(n^3)$;但 $f\notin\Theta(n^3)$,因为 $n^3$ 是个不紧的上界(高估了)。
关于 $n$:$\lim\frac{5n^2+100n}{n}=\infty$,所以 $f\in\omega(n)$,也就 $f\in\Omega(n)$;但 $f\notin O(n)$,这个线性下界同样不紧(低估了)。
关于 $n^2\log n$:$\lim\frac{5n^2+100n}{n^2\log n}=0$,所以 $f\in o(n^2\log n)$。这条提醒我们,$o$ 比 $O$ 更强、更细:同阶函数(如 $f$ 与 $3n^2$)之间有 $O$ 关系但没有 $o$ 关系,因为 $\lim f/g$ 是正常数而非 $0$。

最后是几个最常踩的坑,务必记牢:

$O$ 未必是紧界。 “$f\in O(n^3)$”只是说 $n^3$ 是一个上界,并没断言它就是 $f$ 的真实量级——$5n^2+100n\in O(n^3)$ 完全正确,但具体而误导。要表达”恰好是这个量级”(即上界还是紧的)应当用 $\Theta$。日常说”这个算法是 $O(n^2)$”时,人们心里想的常常是 $\Theta(n^2)$,但写出来的 $O$ 在逻辑上更弱,读者不应据此反推下界。
“$f=O(g)$”里的等号是记号滥用。 严格说 $O(g)$ 是一个函数集合,正确写法是 $f\in O(g)$;教科书里写成 $f=O(g)$ 只是约定俗成的简写。这个”等号”是单向的、不可逆的:可以写 $5n^2=O(n^3)$,但绝不能反过来写 $O(n^3)=5n^2$,也不能从 $f_1=O(n)$、$f_2=O(n)$ 推出 $f_1=f_2$。本文为减少歧义,在精确陈述处一律用 $\in$。
渐近增长率与”最坏/平均情形”是两个正交的约定,勿混。 渐近记号本身只描述”一个数列随 $n$ 怎么增长”,它既可以套在最坏情形函数 $T_{\text{worst}}(n)$ 上,也可以套在平均情形函数 $T_{\text{avg}}(n)$ 上。所以”$O(n\log n)$”这句话本身并不蕴含是最坏还是平均——快速排序最坏 $\Theta(n^2)$、平均 $\Theta(n\log n)$ 就是同一个算法在两种约定下给出不同渐近结果的例子。说清楚一个复杂度结论,必须同时交代清楚:用的是哪种情形(最坏/平均)、哪种资源(时间/空间)、以及哪个渐近记号($O/\Omega/\Theta$)。

回到正题:正因为渐近视角抹掉了常数和低阶项,”在不同计算模型下大致等价”才成为可能——在合理的串行模型之间互相模拟,只会带来多项式级别的开销,因此”是不是多项式时间”这件事在所有这些模型下都不变,这正是下面要建立的多项式时间概念之所以稳健的根基。一个运行时间为 $5n^2+100n$ 的算法,我们粗略记作 $O(n^2)$(更精确地说是 $\Theta(n^2)$),换台机器跑可能变成 $7n^2+30n$,量级丝毫不变——这正是渐近记号要保护的不变量。

多项式时间与”可处理”

有了渐近度量,就可以划出那条最重要的分界线。如果存在常数 $c$,使得算法在规模为 $n$ 的输入上的(最坏情形)运行时间是 $O(n^c)$,我们就说它是多项式时间(polynomial time)的;反之,像 $2^n$、$n!$ 这样增长的就是指数时间。用前面的记号说,多项式时间就是要求 $T_{\text{worst}}(n)\in O(n^c)$ 对某个固定常数 $c$ 成立——注意 $c$ 必须是与 $n$ 无关的常数。像 $n^{\log n}$ 这种”指数随 $n$ 长大”的函数就不是多项式:由 $n^{\log n}=2^{(\log n)^2}$ 可见它的指数 $(\log n)^2$ 随 $n$ 无界增长,故对任何固定的 $c$ 最终都有 $n^{\log n}>n^c$。这类函数是超多项式(super-polynomial)的,更精确地说,它属于拟多项式(quasi-polynomial,即形如 $2^{\,\mathrm{polylog}(n)}$ 的函数);拟多项式只是超多项式的一个真子类,二者并不同义。

把”多项式时间”等同于”实际可解、可处理(tractable)”的这个观念,并非天经地义,而是上世纪六十年代几位先驱明确提出来的。Alan Cobham 在 1965 年的论文《函数的内在计算难度》(The Intrinsic Computational Difficulty of Functions)中,Jack Edmonds 在同年那篇研究一般图最大匹配的名作《路径、树与花》(Paths, Trees, and Flowers)中,不约而同地把多项式时间算法称作”好算法(good algorithm)”,并主张这才是”高效”的恰当数学定义。这一立场后来被称为 Cobham–Edmonds 论题(Cobham–Edmonds thesis)。值得一提的是,Edmonds 那篇匹配论文之所以经典,正是因为它给出了第一个真正多项式的匹配算法,而不是停留在指数级的穷举上——它用实例宣告了”多项式 = 高效”这一标准的可行性。

为什么用多项式这条线,而不是别的?可以从三个层面理解它的稳健性,而这三层稳健性恰好分别来自上面铺垫的不同概念:

一是它对组合稳健(closure):多项式与多项式相加、相乘、复合仍是多项式(若 $p,q$ 都是多项式,则 $p+q$、$p\cdot q$、$p(q(n))$ 也都是),所以把若干高效子程序拼起来,整体仍然高效。这让我们能放心地模块化地设计算法——一个多项式时间的主程序调用多项式次多项式时间的子程序,总开销仍是多项式。
二是它对模型稳健(robustness):如前面讲渐近记号时所述,合理计算模型之间互相模拟只差多项式因子,因此”多项式时间”这个类不依赖于你选哪台理想机器——单带图灵机、多带图灵机、随机存取机(RAM)各自定义出来的”多项式时间可解”是同一个集合。
三是它在经验上分得开(empirical separation):大量自然问题要么有一个不太高的多项式算法($n$、$n^2$、$n^3$),要么人类至今只会指数级的穷举,中间很少有 $n^{100}$ 这种”理论上多项式、实际上不可用”的尴尬例子。

当然要诚实地承认,这只是一个有用的近似:$n^{100}$ 的多项式算法实际上并不可用,而某些指数算法在小规模上反而够用。但作为一道把”原则上可扩展”与”原则上不可扩展”分开的理论分界,多项式时间是迄今最成功、最经得起推敲的选择。把这条线立稳之后,下一步就能在它之上定义 $\mathsf{P}$(确定性图灵机多项式时间可判定的语言)与 $\mathsf{NP}$(非确定性图灵机多项式时间可判定的语言),而前面反复强调的”确定性 vs 非确定性”这条裂缝,正是 $\mathsf{P}$ 与 $\mathsf{NP}$ 之间那道著名鸿沟的源头。

$\mathsf{P}$:多项式时间可判定

由此得到第一个、也是最朴素的复杂度类。$\mathsf{P}$(polynomial time)是所有能被某个确定性图灵机(deterministic Turing machine)在多项式时间内判定的判定问题构成的类。把它写成形式化的语言版本:语言 $L\subseteq{0,1}^*$ 属于 $\mathsf{P}$,当且仅当存在一台确定性图灵机 $M$ 与一个常数 $c$,使得对每个输入 $x$,$M$ 在至多 $

^c+c$ 步内停机,且 $M$ 接受 $x$ 当且仅当 $x\in L$。这里 $

$ 是输入的长度,“判定”意味着对“是”实例($x\in L$)和“否”实例($x\notin L$)都必须给出正确的、停机的回答——$\mathsf{P}$ 这种对两类实例的对称要求,稍后会与 $\mathsf{NP}$ 形成鲜明对照。

直观地说,$\mathsf{P}$ 就是“我们已经知道怎么真正高效地解出来”的那些问题;它常被当作“可处理(tractable)”这一非正式概念的数学代名词。这一身份并非天经地义,而是建立在两条经验性的论据之上:其一,所有合理的串行计算模型(多带图灵机、RAM、各种高级语言)都能彼此多项式时间地相互模拟,因此“多项式时间”这个判据在模型之间是稳健的、不依赖于实现细节的;其二,自然算法的多项式次数往往很小($n,\,n\log n,\,n^2,\,n^3$),而一旦一个问题落入多项式时间,实践中通常很快就能找到次数更低、常数更优的算法。需要提醒的坑是:$\mathsf{P}$ 是一个渐近、最坏情形的概念,$n^{100}$ 这样的多项式在理论上属于 $\mathsf{P}$ 却毫无实用性;反过来,某些指数时间算法在实际输入分布上可能表现良好。把 $\mathsf{P}$ 直接等同于“现实中跑得快”是一种有用的、但需要保留的近似。

$\mathsf{P}$ 的成员极其丰富:排序、最短路径、最大流、线性规划、两个数互质判断,乃至素性判定,最后这一个由 Agrawal、Kayal、Saxena 在 2002 年的 AKS 算法证明属于 $\mathsf{P}$,是这条线持续被推进的著名例子(它表明一个长期只有随机或亚指数算法的问题,最终被纳入确定性多项式时间)。$\mathsf{P}$ 内部的封闭性也很好:它对补运算封闭——若一个语言 $L$ 在 $\mathsf{P}$ 中,它的补 $\overline{L}={0,1}^*\setminus L$ 也在 $\mathsf{P}$ 中,因为只需把判定 $L$ 的图灵机的“接受 / 拒绝”对调即可,多项式时间界不受影响;它也对多项式时间归约封闭(后面会精确定义这种归约)。这些性质让 $\mathsf{P}$ 成为“可处理”这一概念的稳定载体。

$\mathsf{NP}$:多项式时间可验证(等价于非确定性多项式时间)

下一个类是整套理论的真正主角。$\mathsf{NP}$ 有两个等价的定义,理解它们之间为什么等价,几乎就理解了这一节的核心。

第一种是可验证(verifier)的视角,也是最贴近直觉的。我们先把核心对象精确化。称一个判定问题(语言)$L$ 属于 $\mathsf{NP}$,如果存在一台确定性图灵机 $V$(称为验证器,verifier)与两个常数 $c,d$,使得对每个输入 $x$:

(完备性 / completeness)若 $x\in L$,则存在一段字符串 $w$,其长度满足 $ w \le x ^c$,使得 $V$ 在至多 $ x ^d$ 步内停机并接受 $(x,w)$;
(可靠性 / soundness)若 $x\notin L$,则对任何字符串 $w$,$V$ 都拒绝 $(x,w)$。

这段 $w$ 就叫证书(certificate)或见证(witness)。把定义拆开来读,$\mathsf{NP}$ 中证书的三个关键属性是:(一)长度多项式有界——证书的长度满足 $

\le

^c$,不能长到自身就让验证超时;(二)多项式时间可验证——给定 $x$ 与候选证书 $w$,$V$ 在至多 $

^d$ 步内停机,核验只花关于 $

$ 的多项式时间;(三)非对称的存在性要求——“是”实例要求存在至少一个能通过验证的证书,而“否”实例要求不存在任何能蒙混过关的证书。换句话说,$\mathsf{NP}$ 是“答案为真时,存在一个简短的、可被快速核对的理由”的那些问题。

这处不对称值得反复咀嚼:$\mathsf{NP}$ 的定义只对“是”实例承诺有可被快速验证的证书,对“否”实例不作任何对称的承诺。一个“否”实例之所以是“否”,是因为所有候选证书都失败了,而这件“对所有 $w$ 都失败”的全称事实本身,$\mathsf{NP}$ 并不保证有简短证书去佐证。这个偏心正是后面 $\mathsf{co\text{-}NP}$ 的来源,也是 $\mathsf{NP}$ 与 $\mathsf{co\text{-}NP}$ 是否相等这一公开问题的根。

第二种是非确定性(nondeterministic)的视角,也是 $\mathsf{NP}$ 这个名字的出处:一个问题属于 $\mathsf{NP}$,当且仅当它能被一台非确定性图灵机(nondeterministic Turing machine)在多项式时间内判定。所谓非确定性,可以想象成机器在每一步允许同时“猜测”多条分支,展开成一棵深度为多项式的计算树;只要这棵树中存在一条分支在多项式步内进入接受状态,机器就接受输入,反之(所有分支都不接受)才拒绝。注意这里的接受判据天然是“存在一条好分支”,与验证视角里“存在一个好证书”一一对应。

这两种视角是同一回事,证明是直接的双向构造。一方面,给定一台多项式时间非确定机 $N$,把它在某条接受分支上每一步所做的非确定选择按顺序记下来,就得到一段长度多项式有界的字符串;让验证器 $V$ 以这段“选择序列”作为证书 $w$,沿着 $N$ 的规则确定性地复演这一条分支即可在多项式时间内核验——于是 $L\in\mathsf{NP}$ 的验证器定义成立。另一方面,给定一个验证器 $V$ 和它的多项式长度界,构造一台非确定机:先非确定地“猜出”一段长度 $\le

^c$ 的候选证书 $w$(逐位猜,每位二选一),再确定性地运行 $V(x,w)$。当且仅当存在能通过验证的 $w$ 时,才存在一条接受分支。两个方向合起来,就证明了两种定义刻画的是同一个类。

由此 $\mathsf{P}\subseteq\mathsf{NP}$ 是显然的,而且可以严格说清:设 $L\in\mathsf{P}$,有多项式时间确定机 $M$ 判定它。构造一个忽略证书的验证器 $V(x,w):=M(x)$——它根本不读 $w$,自己把 $x$ 重算一遍。于是当 $x\in L$ 时,任取 $w$(例如空串)都能让 $V$ 接受,“存在证书”平凡成立;当 $x\notin L$ 时,对任何 $w$ 都被 $V$ 拒绝。验证器定义的两条都满足,故 $L\in\mathsf{NP}$。一句话:能在多项式时间内直接解出来,自然也能在多项式时间内验证(把证书忽略掉,自己重算一遍即可)。

一个必须钉死的误解:$\mathsf{NP}$ 不是“非多项式”

这里要特别强调一个流传极广、却完全错误的理解:$\mathsf{NP}$ 中的 N 不是 “Non-polynomial(非多项式)”的意思。$\mathsf{NP}$ 的字面来源是 Nondeterministic Polynomial(非确定性多项式时间)。$\mathsf{NP}$ 绝不是“解不出来、超出多项式”的问题集合;恰恰相反,$\mathsf{P}$ 中那些已经高效可解的问题统统也都在 $\mathsf{NP}$ 里(因为 $\mathsf{P}\subseteq\mathsf{NP}$,如上刚刚证过)。$\mathsf{NP}$ 刻画的是“易验证”,而非“难求解”。把 $\mathsf{NP}$ 误读成“非多项式”,会同时酿成两个错误:一是误以为“$\mathsf{NP}$ 问题都很难”,从而完全错失下面 $\mathsf{P}$ 对 $\mathsf{NP}$ 这个问题的真正含义;二是误以为 $\mathsf{P}$ 与 $\mathsf{NP}$ 天然不交,而事实是 $\mathsf{P}$ 是 $\mathsf{NP}$ 的子集,$\mathsf{P}$ 对 $\mathsf{NP}$ 问的恰恰是这个子集是否其实就是全集。

难求解、易验证:SAT、哈密顿回路、子集和

$\mathsf{NP}$ 之所以耐人寻味,在于其中许多问题呈现出鲜明的“求解似乎很难、验证却很容易”的落差。下面三个例子可以逐一对照前述证书的三条属性(多项式长度、多项式时间可验证、只对“是”实例承诺)。

布尔可满足性问题(Boolean satisfiability problem,SAT):给定一个布尔公式 $\varphi(x_1,\dots,x_n)$,问是否存在一组变量赋值使它为真。要找出这组赋值,朴素办法是在 $2^n$ 种赋值里搜索;但若有人递给你一组赋值,你只需把它代入公式逐个连接词求值,就能在多项式时间内核验真假。证书就是那组赋值,长度为 $n$ 位,显然关于输入长度多项式有界;若公式不可满足,则没有任何赋值能让验证通过,可靠性自动成立。
哈密顿回路(Hamiltonian cycle):给定一张图,问是否存在一条经过每个顶点恰好一次再回到起点的回路。可能的回路数量随顶点数呈阶乘级爆炸;但给你一个顶点排列,你只需检查相邻顶点间是否都有边、且每个顶点恰好出现一次,多项式时间足矣。证书就是那条回路(一个顶点排列),长度多项式有界。
子集和(subset sum):给定一组整数和一个目标值,问是否存在一个子集使其元素之和恰好等于目标。子集共有 $2^n$ 个;但给你一个子集(用一个 $n$ 位的选择向量编码),把它们加起来与目标比一下即可,加法和比较都是多项式时间的。证书就是那个子集。

这三个例子都生动体现了 $\mathsf{NP}$ 的精神:幸运地拿到答案后核对很便宜,从零开始把答案找出来却昂贵得多(就目前所知如此)。要强调“就目前所知”:这种落差是我们尚未找到高效求解算法的现状,而非已被证明的下界——是否真的存在这道鸿沟,正是 $\mathsf{P}$ 对 $\mathsf{NP}$ 要问的。

$\mathsf{NP\text{-}complete}$ 与千禧难题 $\mathsf{P}$ vs $\mathsf{NP}$

那么,“找出来”到底是不是真的比“核对”难?这就是整个领域最深的悬念。要比较两个问题的相对难度,我们需要一把统一的尺子,这把尺子就是归约(reduction)。

精确地说,这里用的是多项式时间多对一归约(polynomial-time many-one reduction,又称 Karp 归约):给定语言 $A,B$,称 $A$ 多项式归约到 $B$,记作 $A\le_p B$,如果存在一个多项式时间可计算的函数 $f$,使得对每个输入 $x$ 都有 $x\in A\iff f(x)\in B$。直观含义是:只要有了 $B$ 的多项式时间算法,就能先用 $f$ 把 $A$ 的实例搬到 $B$ 上、再调用 $B$ 的算法,从而高效地解 $A$。因此 $A\le_p B$ 表达的是“$A$ 不比 $B$ 难”。这个关系是自反、传递的——传递性($A\le_p B$ 且 $B\le_p C$ 蕴含 $A\le_p C$,因为两个多项式时间映射复合后仍是多项式时间)正是后面把完全性“像多米诺骨牌一样”传递下去的技术基础。

有了归约,就能精确定义 $\mathsf{NP}$ 中“最难的一档”。$\mathsf{NP\text{-}hard}$(NP-难)指那些“至少和整个 $\mathsf{NP}$ 一样难”的问题:语言 $B$ 是 $\mathsf{NP\text{-}hard}$,当且仅当对每个 $A\in\mathsf{NP}$ 都有 $A\le_p B$(注意 $B$ 本身未必属于 $\mathsf{NP}$)。$\mathsf{NP\text{-}complete}$(NP-完全)则在此之上再要求 $B$ 自己也落在 $\mathsf{NP}$ 之内:即 $B\in\mathsf{NP}$ 且 $B$ 是 $\mathsf{NP\text{-}hard}$。所有 $\mathsf{NP\text{-}complete}$ 问题彼此通过多项式归约可相互转化,因而地位等价;它们是 $\mathsf{NP}$ 这座山的“最高峰”。一个直接而关键的推论是:若某个 $\mathsf{NP\text{-}complete}$ 问题 $B$ 落入 $\mathsf{P}$,则 $\mathsf{P}=\mathsf{NP}$。证明只需一行:任取 $A\in\mathsf{NP}$,由完全性有 $A\le_p B$,把 $f$(多项式时间)与 $B$ 的多项式时间算法复合,就得到 $A$ 的多项式时间算法,故 $\mathsf{NP}\subseteq\mathsf{P}$;再结合 $\mathsf{P}\subseteq\mathsf{NP}$ 即得相等。换句话说,只要其中任何一个有了多项式时间算法,整个 $\mathsf{NP}$ 就随之坍缩进 $\mathsf{P}$。

这一概念的奠基性结果是 Cook–Levin 定理(Cook–Levin theorem):SAT 是 $\mathsf{NP\text{-}complete}$。这个定理之所以是“第一块多米诺骨牌”,在于它必须不借助任何已有的 $\mathsf{NP\text{-}complete}$ 问题、直接从 $\mathsf{NP}$ 的定义出发把任意非确定多项式时间计算编码成一个布尔公式——其核心是用变量描述非确定图灵机在多项式大小的计算表格中每个格子的状态,再用合取范式约束相邻格子必须符合转移规则,从而让“存在接受计算”等价于“公式可满足”。Stephen Cook 在 1971 年的论文《定理证明过程的复杂性》(The Complexity of Theorem-Proving Procedures)中首次证明了这一点;几乎同时,苏联的 Leonid Levin 独立地提出了等价的概念(其工作于 1973 年正式发表),故以二人共同命名。紧接着,Richard Karp 在 1972 年的论文《组合问题间的可归约性》(Reducibility Among Combinatorial Problems)中,利用归约的传递性,把 SAT 的完全性像多米诺骨牌一样传递出去:只要把 SAT 多项式归约到目标问题、并验证目标问题本身在 $\mathsf{NP}$ 中,后者就也是 $\mathsf{NP\text{-}complete}$。他一举证明了包括哈密顿回路、子集和、团(clique)、顶点覆盖(vertex cover)在内的 21 个自然组合问题全都是 $\mathsf{NP\text{-}complete}$;$\mathsf{P}$ 与 $\mathsf{NP}$ 这两个标准记号也正是在 Karp 这篇文章里确立的。今天人们已知的 $\mathsf{NP\text{-}complete}$ 问题数以千计,遍布图论、调度、逻辑、数论等各个角落——这意味着它们一荣俱荣、一损俱损,攻破任意一个就攻破了全部。

于是著名的 $\mathsf{P}$ 对 $\mathsf{NP}$($\mathsf{P}$ versus $\mathsf{NP}$)问题可以一句话说清:$\mathsf{P}$ 是否等于 $\mathsf{NP}$? 也就是,“易验证”是否蕴含“易求解”?由前面的推论,这个问题等价于“某个(从而所有)$\mathsf{NP\text{-}complete}$ 问题是否有多项式时间算法”。如果 $\mathsf{P}=\mathsf{NP}$,那么任何一个 $\mathsf{NP\text{-}complete}$ 问题一旦被攻破,所有“答案可快速核验”的问题都将变得可快速求解,这将彻底改写密码学、优化、人工智能乃至数学证明本身的面貌:在 $\mathsf{P}=\mathsf{NP}$ 的情形下,凡是“一份正确性可被多项式时间验证的证明”所对应的命题,寻找其证明本身也能在多项式时间内完成(因为“是否存在多项式长度的可验证证明”这件事本身就是一个 $\mathsf{NP}$ 问题),于是发现证明与核验证明在效率上将不再有本质鸿沟。绝大多数研究者猜测 $\mathsf{P}\neq\mathsf{NP}$,即这道鸿沟真实存在,但至今无人能证明——而且已有结果表明,若干最自然的证明手段(如相对化、自然证明)在原样使用时都不足以分开二者,这部分解释了它为何如此之难。这个问题在 2000 年被克雷数学研究所(Clay Mathematics Institute)列为七大千禧难题(Millennium Prize Problems)之一,正式问题陈述由 Stephen Cook 撰写,首个正确解答悬赏一百万美元;诸难题于 2000 年 5 月 24 日在巴黎法兰西公学院宣布。它不仅是计算机科学的最大未解之谜,也是当代数学的核心问题之一。

$\mathsf{co\text{-}NP}$ 以及它与 $\mathsf{NP}$ 的关系

最后回到前面埋下的那处不对称。$\mathsf{NP}$ 偏心于“是”实例:它保证“是”实例有简短可验证的证书,对“否”实例不置一词。把视角整个翻转过来,就得到 $\mathsf{co\text{-}NP}$。

精确地说,一个判定问题 $L$ 属于 $\mathsf{co\text{-}NP}$,当且仅当它的补问题 $\overline{L}$(把“是 / 否”对调后的那个问题)属于 $\mathsf{NP}$。把 $\mathsf{NP}$ 的验证器定义对偶化,可以等价地直接刻画 $\mathsf{co\text{-}NP}$:存在多项式时间验证器 $V$ 与常数 $c,d$,使得当 $x\in L$ 时对所有满足 $

\le

^c$ 的 $w$ 都有 $V(x,w)$ 接受,而当 $x\notin L$ 时存在某个满足 $

\le

^c$ 的 $w$ 使 $V(x,w)$ 拒绝。也就是说,$\mathsf{co\text{-}NP}$ 中的问题对每个“否”实例都拥有一段简短、可在多项式时间内核验的证书(一个“反例”),它擅长的是“快速地确认答案为否”。典型代表是重言式问题(tautology,TAUT):给定一个布尔公式,问它是否在所有赋值下都为真。TAUT 是 $\mathsf{co\text{-}NP\text{-}complete}$ 的(可由 SAT 的 $\mathsf{NP\text{-}complete}$ 性对偶得到:$\varphi$ 是重言式当且仅当 $\neg\varphi$ 不可满足),地位恰与 SAT 在 $\mathsf{NP}$ 中的地位相对称:要否定“这是个重言式”,只需出示一组让它为假的赋值即可,这组反例就是“否”方向的简短证书;反过来,要肯定它是重言式,却没有已知的简短证书——这正是 $\mathsf{NP}$ 与 $\mathsf{co\text{-}NP}$ 的核心差异所在。

$\mathsf{NP}$ 与 $\mathsf{co\text{-}NP}$ 之间的关系,是 $\mathsf{P}$ 对 $\mathsf{NP}$ 之外的又一个公开难题。先看已知的事实。由于 $\mathsf{P}$ 对补运算封闭(前已说明),立刻得到 $\mathsf{P}\subseteq\mathsf{NP}\cap\mathsf{co\text{-}NP}$:任取 $L\in\mathsf{P}$,则 $L\in\mathsf{NP}$(因 $\mathsf{P}\subseteq\mathsf{NP}$),且 $\overline{L}\in\mathsf{P}\subseteq\mathsf{NP}$ 故 $L\in\mathsf{co\text{-}NP}$,于是 $L$ 同时落在两者之中。但 $\mathsf{NP}$ 是否对补运算封闭却不得而知——也就是说,$\mathsf{NP}$ 是否等于 $\mathsf{co\text{-}NP}$ 仍是公开问题。学界普遍猜测 $\mathsf{NP}\neq\mathsf{co\text{-}NP}$。这里要把强弱关系说清楚:$\mathsf{NP}\neq\mathsf{co\text{-}NP}$ 是比 $\mathsf{P}\neq\mathsf{NP}$ 更强的猜测——它蕴含 $\mathsf{P}\neq\mathsf{NP}$,而反向的蕴含至今未知。其关键在于下面这个蕴含关系:

\[\mathsf{P}=\mathsf{NP}\;\Longrightarrow\;\mathsf{NP}=\mathsf{co\text{-}NP}.\]

证明很短:若 $\mathsf{P}=\mathsf{NP}$,则因 $\mathsf{P}$ 对补封闭,$\mathsf{NP}=\mathsf{P}$ 也对补封闭,而“对补封闭”正是 $\mathsf{NP}=\mathsf{co\text{-}NP}$ 的定义。取这个蕴含的逆否命题就得到:一旦证明了 $\mathsf{NP}\neq\mathsf{co\text{-}NP}$,就连带证明了 $\mathsf{P}\neq\mathsf{NP}$。换言之,分开 $\mathsf{NP}$ 与 $\mathsf{co\text{-}NP}$ 是比分开 $\mathsf{P}$ 与 $\mathsf{NP}$ 更艰巨(至少不更容易)的任务。直观上,$\mathsf{NP}\neq\mathsf{co\text{-}NP}$ 表达的是一种更深的不对称:存在一些命题(比如某些重言式,或某些公式的不可满足性),它们即便为真,也未必拥有任何简短的证明——这一信念正是命题证明复杂性(proof complexity)这整门学科的出发点,该领域研究各类证明系统中重言式所需证明的长度下界,而 $\mathsf{NP}\neq\mathsf{co\text{-}NP}$ 恰等价于“不存在能为所有重言式给出多项式长度证明的证明系统”。

至此,地基已经打好。我们有了度量难度的统一对象(判定问题)与统一尺度(最坏情形、渐近、多项式时间),有了 $\mathsf{P}$ 这个“可处理”的标尺,有了 $\mathsf{NP}$ 这个“易验证”的核心舞台及其最难的一档 $\mathsf{NP\text{-}complete}$,有了横亘其上的 $\mathsf{P}$ 对 $\mathsf{NP}$ 千禧难题,也有了刻画“易否证”的 $\mathsf{co\text{-}NP}$ 及其同样悬而未决的对称之问。带着这套语言,后面才能继续走向 $\mathsf{PSPACE}$、$\mathsf{#P}$,以及在算法博弈论中举足轻重的 $\mathsf{PPAD}$、$\mathsf{PLS}$ 等更精细的复杂度类。

归约：难度是如何被“传染”的

如果说复杂度类（complexity class）是把问题按难度分门别类的“地图”，那么归约（reduction）就是丈量这张地图的尺子。它是整个计算复杂性理论里最核心、也最具杠杆效应的工具：一旦我们手里握有归约，就可以用一个问题的难度去“框定”另一个问题的难度，从而把对单个问题的孤立分析，编织成一张相互牵制的难度网络。在没有归约之前，“这个问题难”只是一句感叹；有了归约之后，“难”成了一个可以在问题之间传递、比较、累积的结构性关系。本节要把这把尺子的刻度讲清：归约的精确定义、它传递难度的方向、它的传递性、为什么转换过程必须受多项式时间限制，以及它如何被用来定义“难（hard）”与“最难（complete）”。

归约的基本思想：把 A 搬到 B 身上去解

归约的直觉非常朴素。假设我们想解问题 A，但手头只有一台能解问题 B 的“机器”。如果我们能找到一个高效的转换过程，把 A 的任意一个实例（instance）改写成 B 的一个实例，并保证两者的答案一致，那么我们就可以借助解 B 的机器来解 A。这件事一旦成立，逻辑上立刻推出一句关键的话：

B 不会比 A 更容易。

为什么是这个方向？我们不妨把推理写得更细一点。归约给了我们一条蕴含链：“会解 B” $\Rightarrow$ “会解 A”。对这条蕴含取逆否命题，就得到 “不会解 A” $\Rightarrow$ “不会解 B”。把“会解”理解为“存在高效算法”，两句话分别说的是：

若 B 容易（有多项式时间算法），则 A 也容易——因为先用转换函数改写实例、再调用 B 的算法，整条流程仍是多项式时间；
若 A 困难（无多项式时间算法），则 B 也必然困难——否则上一条会推出 A 容易，与“A 困难”矛盾。

难度正是沿着归约的方向被“传染”过去的：把已知困难的 A 归约到 B，困难性就传给了 B；反之，把待解的 A 归约到已知容易的 B，则容易性传回给 A。初学者最容易搞反方向（误以为“A 归约到 B”是用 A 去解 B），所以记住这句口诀就够了：“我会把困难的问题 A 伪装成你 B，所以你 B 也得困难。” 谁被伪装成谁，难度就从被伪装者流向伪装的目标。

这里有一个容易忽略但至关重要的前提：转换本身必须比目标问题“便宜”。如果改写实例的过程本身就需要指数时间，那这台“机器”就没有任何意义了——因为“先做指数时间的转换、再调用一次 B”整体已经是指数时间，即便 B 有多项式算法也救不回来。换句话说，归约能保持的“容易性”，受限于归约本身消耗的资源：只有当转换比我们关心的难度界限更廉价时，归约才能真正传递这一层级的难度。因此在 NP 完全性（NP-completeness）的语境里，我们要求转换过程在多项式时间内完成；如果研究的是更精细的层级（例如对数空间内的归约 $\le_{\log}$，用来区分 $\mathsf{NL},\mathsf{P}$ 等类），就会换用更严格的资源限制。归约的资源限制，决定了它能区分哪一层级的难度：尺子的刻度不能比要测量的对象还粗。

两种归约：多对一（Karp）与 Turing（Cook）

归约不止一种，区别在于“允许怎样使用解 B 的机器”。

第一种是多对一归约（many-one reduction），因为通常要求转换函数在多项式时间内计算，又称 Karp 归约（Karp reduction），以理查德·卡普（Richard Karp）命名。它最为“简朴”：存在一个多项式时间可计算的函数 $f$，把 A 的实例 $x$ 映射成 B 的实例 $f(x)$，并保证

\[x \in A \iff f(x) \in B.\]

把这条等价式拆成两个方向，含义会更清楚：

正确性（完备方向）：$x\in A \Rightarrow f(x)\in B$，即 A 的每个“是”实例都被映到 B 的某个“是”实例；
正确性（可靠方向）：$x\notin A \Rightarrow f(x)\notin B$，即 A 的每个“否”实例都被映到 B 的某个“否”实例。

两个方向缺一不可——只保证前者，会让 A 的“否”实例可能被误映成 B 的“是”实例，从而读出错误答案。注意 $f$ 不必是单射，多个不同的 A-实例完全可以被映到同一个 B-实例，“多对一（many-one）”之名正源于此。整个过程只调用一次解 B 的机器，且把它的答案原封不动地当作 A 的答案，中途不做任何额外加工。记号上常写作 $A \le_p B$（读作“A 多项式时间多对一归约到 B”），下标 $p$ 强调转换的多项式时间限制。

第二种是 Turing 归约（Turing reduction），在多项式时间语境里又称 Cook 归约（Cook reduction），以斯蒂芬·库克（Stephen Cook）命名。它把解 B 的机器当成一个可以反复调用的神谕（oracle）：解 A 的算法是一台多项式时间的确定型图灵机，运行过程中可以对 B 提出多项式数量的询问，而且后一个询问可以依赖前面询问的答案（自适应查询，adaptive queries），最后再综合所有回答给出 A 的结论。记号上常写作 $A \le^{\mathrm{p}}T B$（下标 $T$ 表示 Turing 式归约、上标 $\mathrm{p}$ 表示多项式时间，与前面的 $\le_p,\le{\log}$ 同属一套资源—类型记号约定）。直观地说，Karp 归约是“一锤子买卖”——改写一次、问一次、照搬答案；Cook 归约则允许“边问边想”——可以问很多次，还可以对得到的答案做任意多项式时间的后处理（包括取反）。如果限制各次询问必须事先一次性给出、彼此不依赖回答，就得到所谓非自适应（non-adaptive）归约，又称真值表归约（truth-table reduction），介于 Karp 与一般 Cook 之间；本文不展开这一精细谱系。

两者的关系很清楚：每个 Karp 归约自动是一个 Cook 归约（“只问一次、直接采用答案”本就是“可以多次提问、并做后处理”的一个特例），因此 Karp 归约是更严格、限制更强的概念。正是这种严格性带来了好处。Karp 归约保持了“是/否”结构——它不能把“是”翻成“否”，因为答案被原样采用——因此在它之下，一个 $\mathsf{NP}$ 完全问题不会自动与其补问题互归约，从而 $\mathsf{NP}$ 完全与 $\mathsf{co\text{-}NP}$ 完全在这把尺子下不会自动重合（至于 $\mathsf{NP}$ 是否等于 $\mathsf{co\text{-}NP}$，这本身仍是一个公开问题，Karp 归约并不能解答它）。而 Cook 归约由于允许取反（先问 B、再把答案否定），会让一个 $\mathsf{NP}$ 完全问题与它的补问题在该归约下彼此可归约，于是 $\mathsf{NP}$ 完全与 $\mathsf{co\text{-}NP}$ 完全之间的这一区分被抹平。也因此，自卡普 1972 年的工作之后，NP 完全性的标准定义采用的是多对一的 Karp 归约，而不是库克最初使用的 Turing 式归约。这一段历史本身就很有意思：库克在 1971 年最早提出 NP 完全性时，用的是多项式时间版本的 Turing 归约（类比可计算性理论里的图灵归约）；一年后卡普改用多项式时间版本的多对一归约重新定义，这个定义此后成为通行标准。除非特别说明，本文之后所说的“归约”默认都指 Karp 归约 $\le_p$。

用归约定义 hardness 与 completeness

有了归约这把尺子，“难”和“最难”就可以被精确地定义出来，而不再是含糊的直觉。固定一个复杂度类 $\mathsf{C}$（例如 $\mathsf{NP}$），并固定一种归约（通常是 Karp 归约 $\le_p$）：

$\mathsf{C}$-难（$\mathsf{C}$-hard）：问题 $B$ 称为对类 $\mathsf{C}$ 是难的，如果 $\mathsf{C}$ 中每一个问题 $A$ 都满足 $A\le_p B$。换句话说，$B$ 至少和 $\mathsf{C}$ 里所有问题一样难，它“承接”了整个 $\mathsf{C}$ 的全部难度。注意 $\mathsf{C}$-hard 并不要求 $B$ 本身属于 $\mathsf{C}$，它可能严格更难：例如某些 $\mathsf{PSPACE}$ 完全问题（如量化布尔公式的真值判定 TQBF/QBF）是 $\mathsf{NP}$-hard 的，但被广泛相信不属于 $\mathsf{NP}$——若它们当真属于 $\mathsf{NP}$，就会推出 $\mathsf{NP}=\mathsf{PSPACE}$，与普遍信念相悖。（要小心：单凭“某问题属于 $\mathsf{PSPACE}$”并不能说明它不在 $\mathsf{NP}$ 里，因为 $\mathsf{NP}\subseteq\mathsf{PSPACE}$；真正能把 $B$“顶”到 $\mathsf{NP}$ 之外的，是它对 $\mathsf{PSPACE}$ 的完全性。）
$\mathsf{C}$-完全（$\mathsf{C}$-complete）：问题 $B$ 称为对类 $\mathsf{C}$ 是完全的，如果它既是 $\mathsf{C}$-难，又确实属于 $\mathsf{C}$。

这里有一个常被忽视的隐含要求：用来定义完全性的归约，其能力必须弱于（或至多等于）类 $\mathsf{C}$ 本身。直觉上，如果允许的归约比 $\mathsf{C}$ 还强，那么“最难”这个判断就失去了意义——一把比被测物还粗的尺子量不出内部的高低。这也是为什么定义 $\mathsf{NP}$ 完全性时用多项式时间归约（它弱于我们想区分的 $\mathsf{P}$ 与 $\mathsf{NP}$ 之别），而非更强的归约。

把这两条放在一起品味，$\mathsf{C}$-完全的问题就是 $\mathsf{C}$ 里“最难的那一批”：它们坐落在 $\mathsf{C}$ 的内部（不会比 $\mathsf{C}$ 更难），同时又困难到足以代表整个 $\mathsf{C}$。这一刻归约的威力才真正显现：$\mathsf{C}$-完全问题成了整个复杂度类的“代言人”。如果你能为某一个 $\mathsf{NP}$ 完全问题找到多项式时间算法，那么凭借归约，$\mathsf{NP}$ 里所有问题都立刻有了多项式时间算法（每个 $A\in\mathsf{NP}$ 先用 $f$ 转成该完全问题的实例，再调用那个假想的高效算法），于是 $\mathsf{P}=\mathsf{NP}$。反过来，只要相信 $\mathsf{P}\ne\mathsf{NP}$，就等于相信没有任何一个 $\mathsf{NP}$ 完全问题存在高效算法。成千上万个看似毫不相干的问题，因此被归约捆在了同一根命运的绳子上：它们要么一起容易，要么一起困难。

库克-列文定理：第一块多米诺骨牌

上面的框架有一个隐含的前提没有交代：要证明某个 $B$ 是 $\mathsf{NP}$ 完全的，按定义需要把 $\mathsf{NP}$ 中每一个问题都归约到 $B$，可 $\mathsf{NP}$ 里有无穷多个问题，怎么可能一一去做？

这正是 库克-列文定理（Cook-Levin theorem） 解决的问题。1971 年，斯蒂芬·库克在论文 The Complexity of Theorem-Proving Procedures 中证明了：布尔可满足性问题（Boolean satisfiability problem，简称 SAT）是 NP 完全的。几乎同时，苏联的列昂尼德·列文（Leonid Levin）独立地定义了 NP 完全性并证明了一个 SAT 变体的完全性（他的论文 1973 年发表，但 1971 年起已在报告中讲述这些结果），因此该定理冠以两人之名。

这个证明的精妙之处在于它的普适性：库克没有逐个去归约 $\mathsf{NP}$ 里的问题，而是抓住了 $\mathsf{NP}$ 的定义本身。$\mathsf{NP}$ 中任意一个问题 $A$，按定义都有一台多项式时间的非确定型图灵机 $M_A$ 来验证它的“是”实例（即 $x\in A$ 当且仅当 $M_A$ 在输入 $x$ 上存在一条接受的计算路径）。库克证明，对任意输入 $x$，机器 $M_A$ 在多项式步数内的整个计算过程，都可以被系统性地编码成一个布尔公式 $\varphi_{M_A,x}$——用布尔变量描述每一时刻每一格的纸带符号、读写头位置与状态，用子句约束“相邻两步必须符合 $M_A$ 的转移规则”“初始格局对应输入 $x$”“某一步进入接受状态”——使得“$M_A$ 在 $x$ 上存在一条接受的计算路径”恰好对应“$\varphi_{M_A,x}$ 可满足”。这个编码本身可在多项式时间内构造，因此它正是一个从 $A$ 到 SAT 的 Karp 归约。由于这套编码对 $\mathsf{NP}$ 中所有问题统一适用，SAT 便一举承接了整个 $\mathsf{NP}$ 的难度。

库克-列文定理的真正意义，是它提供了第一块多米诺骨牌：在它之前，证明 $\mathsf{NP}$ 完全性需要面对“无穷多个问题”的窘境；在它之后，要证明一个新问题 $B$ 是 $\mathsf{NP}$ 完全的，只需做两件事——先说明 $B$ 属于 $\mathsf{NP}$（给出一个多项式时间的验证器，即一个长度多项式的“证书”能在多项式时间内被核验），再把某一个已知的 $\mathsf{NP}$ 完全问题（最方便的就是 SAT，或它的受限形式 3-SAT）归约到 $B$。归约的传递性在这里是关键支撑：若 $A\le_p B$ 且 $B\le_p C$，则 $A\le_p C$。其证明也很直接——若 $f$ 是 $A\to B$ 的归约、$g$ 是 $B\to C$ 的归约，则复合 $g\circ f$ 满足 $x\in A \iff f(x)\in B \iff g(f(x))\in C$，而两个多项式时间函数的复合仍是多项式时间。于是一旦把 SAT 归约到 $B$，SAT 所承接的整个 $\mathsf{NP}$ 难度就顺着这条链一路传到 $B$。证明 $\mathsf{NP}$ 完全性，从此从“对抗无穷”变成了“做一次归约”。

经典归约链：从一个困难问题繁衍出一片

第一块骨牌一旦立起，整片骨牌就开始倒下。最常被引用的起点是 3-SAT（每个子句恰含三个文字的可满足性问题，它同样是 $\mathsf{NP}$ 完全的——可由 SAT 经一个标准的“拆长子句”归约得到），由它出发可以连出一条经典归约链：

\[\text{3-SAT} \le_p \text{Clique} \le_p \text{Vertex Cover} \cong \text{Independent Set} \le_p \cdots\]

其中团（Clique，判定图中是否存在大小为 $k$ 的两两相连顶点集）、顶点覆盖（Vertex Cover，判定是否存在大小 $\le k$ 的覆盖所有边的顶点集）、独立集（Independent Set，判定是否存在大小 $\ge k$ 的两两不相连顶点集） 这三个图论问题彼此之间的关系尤其优美，它们本质上是同一枚硬币的不同面：

一个顶点集 $S$ 是图 $G$ 的独立集，当且仅当它在补图（complement graph，把所有边取反得到的图） $\bar{G}$ 中是一个团。理由很直接：$S$ 在 $G$ 中两两不相连，等价于这些顶点对在 $\bar{G}$ 中两两相连。于是“$G$ 中有大小 $k$ 的独立集”当且仅当“$\bar{G}$ 中有大小 $k$ 的团”，构造 $\bar{G}$ 显然是多项式时间的。

一个顶点集 $S$ 是独立集，当且仅当它的补集 $V\setminus S$ 是一个顶点覆盖。理由是：$S$ 独立 $\iff$ 没有任何一条边的两个端点都落在 $S$ 里 $\iff$ 每条边至少有一个端点落在 $V\setminus S$ 里 $\iff$ $V\setminus S$ 覆盖了所有边。两个方向都成立，所以这是一条精确的等价。由此“$G$ 有大小 $\ge k$ 的独立集”当且仅当“$G$ 有大小 $\le n-k$ 的顶点覆盖”（$n=

$）。

这两条等价关系几乎不需要任何“构造”，仅靠取补图、取补集就完成了归约（记号 $\cong$ 即强调这种双向归约带来的“难度等价”），是体会“难度等价”最干净的例子。

另一条同样著名的链通向数值问题：

\[\text{3-SAT} \le_p \text{子集和（Subset Sum）} \le_p \text{背包（Knapsack）},\]

它揭示了一个常被误解的事实：$\mathsf{NP}$ 困难并不限于图论或逻辑，连“给定一堆整数，能否选出一个子集使其和恰为目标值”这样纯算术的问题，本质上也和 SAT 一样难。难度的传染跨越了问题的外观差异。这里需要厘清这条链里难度究竟由哪一步承载：其中 $\text{Subset Sum} \le_p \text{Knapsack}$ 是平凡的特例化——判定版背包只需令每个物品的价值等于其重量、再把容量和价值阈值都设为目标值 $W$，就退化成子集和——它本身不“产生”新难度；真正完成难度传递、把 SAT 的困难性注入这片数值世界的，是 $\text{3-SAT} \le_p \text{Subset Sum}$ 这一步。顺带一提，子集和与背包都是所谓弱 $\mathsf{NP}$ 完全（weakly NP-complete）问题：它们有伪多项式时间（pseudo-polynomial，即关于数值大小而非输入比特长度多项式）的动态规划算法。这与强 $\mathsf{NP}$ 完全（strongly NP-complete）问题形成对照——后者即便把出现的所有数值都限制在输入规模的多项式范围内（或干脆不含大数值参数）也依然困难，典型代表是团、顶点覆盖这类纯组合的图论问题。需要强调的是，强/弱 $\mathsf{NP}$ 完全是针对带数值参数的问题才有意义的精细区分；像 3-SAT 这样根本不含数值参数的问题，并不落在这个数值二分的语境之内。这一区分提醒我们，“$\mathsf{NP}$ 完全”内部仍有更细的纹理。

两个归约的构造直觉

抽象的定义不如看一眼“齿轮（gadget）”是怎么咬合的。归约的工程核心，往往就是设计一组小部件（gadget），让源问题的逻辑结构被目标问题的语言忠实地“复刻”出来。下面两个例子都要落实归约的双向正确性：源问题的“是”当且仅当目标问题的“是”。

例一：3-SAT 归约到 Clique。 给定一个有 $k$ 个子句、每个子句三个文字的 3-SAT 公式 $\phi$，我们构造一个图 $G$：为每个子句里的每个文字造一个顶点（于是共 $3k$ 个顶点，按子句分成 $k$ 组，每组 $3$ 个）。连边规则有两条：（1）同一个子句内部的三个顶点互不连边；（2）位于不同子句的两个文字顶点，只要它们不互相矛盾（不是像 $x$ 与 $\lnot x$ 这样的取反对），就连一条边。这个构造显然是多项式时间的（顶点数 $3k$，边数至多 $\binom{3k}{2}=O(k^2)$）。关键结论是：$G$ 存在大小为 $k$ 的团，当且仅当 $\phi$ 可满足。我们把两个方向都验证一遍：

（$\phi$ 可满足 $\Rightarrow$ 有 $k$ 团） 取一个满足赋值。每个子句至少有一个为真的文字；在每个子句里各挑一个为真的文字对应的顶点，共得 $k$ 个顶点（每组一个）。这 $k$ 个顶点两两相连吗？它们来自不同子句（满足规则 1 的前提），又因为都在同一个赋值下为真，所以不可能出现 $x$ 真且 $\lnot x$ 真的矛盾对——于是规则 2 保证它们两两有边。这正是一个 $k$ 团。
（有 $k$ 团 $\Rightarrow$ $\phi$ 可满足） 设 $C$ 是大小 $k$ 的团。由规则 1，团内顶点必来自 $k$ 个不同的组（同组无边，无法同处一团），故 $C$ 恰好从每个子句各取一个文字顶点。由规则 2，$C$ 中不含任何矛盾对，于是我们可以一致地把 $C$ 选中的所有文字都置为真（不会要求某变量同时为真和为假），其余变量随意取值。这样每个子句都有 $C$ 选中的那个文字为真，故每个子句被满足，$\phi$ 可满足。

两个方向都成立，归约正确。这里的“齿轮”是：分组结构强制“每个子句各选一个文字”，矛盾边的缺失强制“所选文字赋值一致”，二者合起来恰好刻画了满足赋值。

例二：从子句到三角形的部件。 在经典的 3-SAT 归约到顶点覆盖的构造里，部件思想体现得更直白，由两类 gadget 拼成：

变量部件：为每个变量 $x_i$ 造一对顶点 $u_i,\bar{u}_i$（分别代表“取真”“取假”），并在它们之间连一条边。要覆盖这条边，至少得选 $u_i,\bar{u}_i$ 之一——这一步强制“为每个变量做一次真/假的选择”。
子句部件：为每个子句造三个顶点，并把它们连成一个三角形。覆盖一个三角形的三条边，至少需要选其中 $2$ 个顶点。
连接边：把每个子句三角形的三个顶点，分别连到它对应的三个文字（即对应的 $u_i$ 或 $\bar{u}_i$）上。

设公式有 $n$ 个变量、$m$ 个子句，把目标覆盖大小设为 $t=n+2m$（变量部件贡献 $n$，子句部件贡献 $2m$）。结论是：$G$ 存在大小 $\le n+2m$ 的顶点覆盖，当且仅当 $\phi$ 可满足，两个方向同样要核验：

（$\phi$ 可满足 $\Rightarrow$ 有大小 $n+2m$ 的覆盖） 取一个满足赋值。在每个变量部件里，选中“被赋为真的那个文字顶点”（共 $n$ 个），覆盖所有 $n$ 条变量边。对每个子句，它至少有一个文字在该赋值下为真，于是其三角形里那个对应为真文字的顶点，其连接边已被另一端（那个已选中的为真文字顶点）覆盖；因此在这个三角形里，我们只选取其余两个顶点——也就是那两个对应文字未被赋真的三角形顶点。这两个顶点足以覆盖三角形的三条内部边；而剩下的两条连接边（即从这两个被选顶点引出的那两条）也由它们自身覆盖。如此每个三角形各选 $2$ 个、共 $2m$ 个。合计恰 $n+2m$，且逐边检查可知所有边——变量边、三角形内部边、三类连接边——都被覆盖。
（有大小 $n+2m$ 的覆盖 $\Rightarrow$ $\phi$ 可满足） 任何覆盖都必须在每个变量部件选 $\ge 1$ 个、每个子句三角形选 $\ge 2$ 个，下界已是 $n+2m$；既然总数恰为 $n+2m$，必是每个变量部件恰选 $1$ 个、每个三角形恰选 $2$ 个。把“变量部件选中的那个顶点”读作该变量的真假赋值（一致，因为每个部件只选一个）。每个三角形里有一个顶点没被选，它那条通向某文字顶点的连接边必须由文字顶点那一端来覆盖，这说明该文字顶点被选中、即该文字为真——于是这个子句被满足。对所有子句皆然，故 $\phi$ 可满足。

变量部件负责“做一致的真假选择”，子句部件负责“检查每个子句至少被满足一次”，两类齿轮咬合在一起，就把逻辑可满足性精确翻译成了图上的覆盖问题。

这两个例子共同传达了归约的工艺本质：它不是模糊的类比，而是一套可验证的、双向严丝合缝的翻译，源问题的“是/否”必须精确对应目标问题的“是/否”，一个反例都不能漏。证明归约正确，标准动作永远是把 $\iff$ 的两个方向分别写清——漏掉任何一边，归约都不成立。

卡普的 21 个问题与《计算机与难解性》

如果说库克-列文定理点燃了引信，那么真正引爆整个领域、让 NP 完全性从一个孤立结论变成普遍现象的，是理查德·卡普 1972 年的论文 Reducibility Among Combinatorial Problems。卡普以库克的 SAT 完全性为起点，用一连串多项式时间多对一归约，一口气证明了 21 个组合与图论问题都是 NP 完全的，其中就包括团、顶点覆盖、哈密顿回路（Hamiltonian cycle）、集合覆盖、背包等今天家喻户晓的问题。这些归约彼此串联（许多问题不是直接从 SAT、而是从链上更早的问题归约而来），正是上文“传递性”的大规模实战演示。这篇论文的冲击力在于它揭示出：NP 完全性绝不是 SAT 的个别怪癖，而是一种横跨众多重要计算问题的普遍属性。从此，“这个问题是不是 NP 完全的”成了算法设计者面对一个新问题时几乎本能的第一问。

把这套方法论沉淀为整个领域共同语言的，是迈克尔·加里（Michael Garey）与大卫·约翰逊（David Johnson）1979 年的经典著作 《Computers and Intractability: A Guide to the Theory of NP-Completeness》（计算机与难解性：NP 完全性理论指南）。这本书不仅系统讲解了归约技术与证明范式，还在附录里收录了一份长长的 NP 完全问题清单，成为数十年来研究者查证、引用、起步的标准案头工具。直到今天，当一个人想证明手头的新问题困难时，标准动作仍然是，翻开这份清单，挑一个最像的已知 NP 完全问题，设计一个归约，让难度顺着这把尺子，再一次被传染过去。

最后值得点出的是，归约作为工具的意义远不止于 $\mathsf{NP}$。同一套“用归约定义难与完全”的逻辑，被原样搬到了其他复杂度类上，孕育出 $\mathsf{PSPACE}$ 完全（PSPACE-complete）、$\mathsf{#P}$ 完全（#P-complete，计数问题的最难者）、$\mathsf{PPAD}$ 完全（PPAD-complete，纳什均衡等不动点求解问题的归宿）、$\mathsf{PLS}$ 完全（PLS-complete，局部搜索问题的最难者）等一系列概念。每换一个目标复杂度类，往往就要相应调整归约的资源限制（前文已强调，定义完全性的归约能力须弱于该类本身），但“最难代言人”的骨架始终不变。归约一旦被发明，难度就有了可以在整张复杂度地图上自由流动、彼此牵引的通道，这正是它在整个理论中占据核心位置的原因。

NP 之外:多项式层级、PSPACE、EXP、#P

到目前为止,我们的地图上只有 $\mathsf{P}$ 与 $\mathsf{NP}$ 两块大陆,中间隔着那道著名的、尚未证明存在的鸿沟。但计算复杂性的世界远不止于此。一旦我们把”验证一个证据”换成”在证据之间反复博弈”、把”时间”换成”空间”、把”是否存在解”换成”有多少个解”,就会浮现出一整片层峦叠嶂的地貌。本节把地图画大,沿着公认的包含链

\[\mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PH}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}\]

一路向上,介绍多项式层级(polynomial hierarchy, $\mathsf{PH}$)、多项式空间类(polynomial space, $\mathsf{PSPACE}$)、指数时间类(exponential time, $\mathsf{EXP}$ / $\mathsf{EXPTIME}$)与计数类(counting class)$#\mathsf{P}$,并指出这条链上几乎所有的包含到底”是不是真包含”至今仍是公开问题。读这一节时,有一个统一的视角值得始终记在心里:不同的复杂度类,本质上是在用不同的资源(时间/空间)去度量不同的逻辑结构(存在/全称/计数),而我们对这些资源彼此之间的换算关系,大多数时候只有猜想,没有证明。

先把 co-NP 重新展开

回忆一下:$\mathsf{NP}$ 中的问题,其”是”的回答可以用一个简短证据来验证(存在一个满足赋值,你把它念给我听,我一查便信)。更精确地说,语言 $L\in\mathsf{NP}$,当且仅当存在一个多项式时间可判定的关系 $V$ 和一个多项式 $p$,使得

\[x\in L\iff \exists y,\ |y|\le p(|x|),\ V(x,y)=1.\]

这里 $y$ 是”证据”(certificate),$V$ 是”验证器”(verifier)。$\mathsf{co\text{-}NP}$(complement of $\mathsf{NP}$)则相反,它装的是 $\mathsf{NP}$ 问题的”补”,即 $L\in\mathsf{co\text{-}NP}$ 当且仅当 $\overline{L}\in\mathsf{NP}$;这里要被高效验证的是”否”的回答,其结构相应地变成

\[x\in L\iff \forall y,\ |y|\le p(|x|),\ V(x,y)=1.\]

典型代表是重言式问题(TAUTOLOGY):给定一个布尔公式,判断它是否对所有赋值都为真。注意这件事的逻辑结构:”对所有赋值都成立”。$\mathsf{NP}$ 的代表问题 SAT 是”存在一个赋值使公式为真”(一个存在量词 $\exists$),而 TAUTOLOGY 是”对所有赋值公式都为真”(一个全称量词 $\forall$)。事实上 SAT 与 TAUTOLOGY 互为对偶:公式 $\varphi$ 是重言式,当且仅当 $\neg\varphi$ 不可满足。这一存一全的对偶,正是 $\mathsf{NP}$ 与 $\mathsf{co\text{-}NP}$ 的本质区别,也正是下面整座层级的种子。

这里有两个容易踩的坑要澄清。其一,$\mathsf{co\text{-}NP}$ 不是 $\mathsf{NP}$ 的”补集”;它是”由 $\mathsf{NP}$ 语言取补而得的那些语言所组成的类”,两者作为类是高度重叠的(例如所有 $\mathsf{P}$ 中的语言既在 $\mathsf{NP}$ 也在 $\mathsf{co\text{-}NP}$,因为 $\mathsf{P}$ 对取补封闭)。其二,人们普遍相信 $\mathsf{NP}\neq\mathsf{co\text{-}NP}$,但这同样未被证明;一个直观理由是:对”否”的回答(例如”这个公式不可满足”)似乎找不到一般性的短证据。值得强调的是 $\mathsf{NP}\neq\mathsf{co\text{-}NP}$ 比 $\mathsf{P}\neq\mathsf{NP}$ 更强:若 $\mathsf{P}=\mathsf{NP}$,则因 $\mathsf{P}$ 对取补封闭立刻得到 $\mathsf{NP}=\mathsf{co\text{-}NP}$;反过来不成立。因此一旦证明了 $\mathsf{NP}\neq\mathsf{co\text{-}NP}$,就顺带证明了 $\mathsf{P}\neq\mathsf{NP}$。

多项式层级:把量词一层层叠上去

如果一个存在量词给出 $\mathsf{NP}$、一个全称量词给出 $\mathsf{co\text{-}NP}$,那么把存在与全称交替地叠加起来,会得到什么?这就是多项式层级,由 Larry Stockmeyer 在 1976 年的论文 The polynomial-time hierarchy 中系统提出(它是递归论中 Kleene 算术层级的”多项式时间版翻版”:把”递归可枚举”换成”非确定多项式时间”,把”算术关系”换成”多项式时间可判定关系”)。

$\mathsf{PH}$ 用带交替量词的问题来刻画,逐层定义如下。最底层 $\Sigma_0^p=\Pi_0^p=\mathsf{P}$。往上每一层:

$\Sigma_k^p$ 装的问题形如

\[x\in L\iff \exists y\_1\,\forall y\_2\,\exists y\_3\cdots Q\_k y\_k\ \ V(x,y\_1,\dots,y\_k)=1,\]

共 $k$ 个交替量词、以 $\exists$ 打头($Q_k$ 当 $k$ 为奇时是 $\exists$、为偶时是 $\forall$),其中 $V$ 是多项式时间可判定的关系,且每个 $y_i$ 的长度都被输入规模 $|x|$ 的某个多项式所限制(否则 $\forall y$ 可以遍历指数多的串而不受控);

$\Pi_k^p$ 则以 $\forall$ 打头,定义完全对称,是 $\Sigma_k^p$ 的补类,即 $\Pi_k^p=\mathrm{co}\text{-}\Sigma_k^p$。

于是 $\Sigma_1^p=\mathsf{NP}$(一个 $\exists$),$\Pi_1^p=\mathsf{co\text{-}NP}$(一个 $\forall$);$\Sigma_2^p$ 是”$\exists\forall$”型问题,$\Pi_2^p$ 是”$\forall\exists$”型问题,如此层层向上。这里一个关键的、与下文 $\mathsf{PSPACE}$ 形成对照的限制是:层数 $k$ 是一个固定的常数,与输入规模无关;同一层内量词块的个数不随 $n$ 增长。

一个等价且更具操作性的定义是用神谕(oracle)给出的。所谓”带 $\mathcal{C}$ 神谕的机器”,是指一台图灵机额外配备了一个”提问窗口”,可以在一步之内免费得到任意一个 $\mathcal{C}$ 中问题的”是/否”答案。在这套语言下,$\mathsf{PH}$ 的递推刻画极为简洁:

\[\Sigma\_0^p=\mathsf{P},\qquad \Sigma\_{k+1}^p=\mathsf{NP}^{\Sigma\_k^p},\qquad \Pi\_{k+1}^p=\mathrm{co}\text{-}\Sigma\_{k+1}^p.\]

也就是说,$\Sigma_{k+1}^p$ 是”带一个 $\Sigma_k^p$ 神谕的非确定多项式时间”所能解决的问题类;你在已经能免费查询第 $k$ 层答案的前提下,再加一层非确定的猜测能力。验证一下底层:$\Sigma_1^p=\mathsf{NP}^{\mathsf{P}}=\mathsf{NP}$(给 $\mathsf{NP}$ 配一个 $\mathsf{P}$ 神谕不增能力),与量词刻画一致。整个层级定义为

\[\mathsf{PH}=\bigcup\_{k\ge 0}\Sigma\_k^p=\bigcup\_{k\ge 0}\Pi\_k^p.\]

这套刻画的好处是它直接对应许多自然的、”嵌套博弈”或”双层优化”式的问题。一个标准的 $\Sigma_2^p$ 完全问题是 $\Sigma_2$-SAT:给定公式 $\varphi(x,y)$,问”是否存在 $x$,使得对所有 $y$,$\varphi(x,y)$ 都为真”。再如极小极大(minimax)、双层优化(bilevel optimization)、鲁棒优化中的许多判定问题(“是否存在一个我的决策,使得在对手的最坏回应下我仍达标”)都恰好完整地落在 $\mathsf{PH}$ 的某一层(往往是第二层 $\Sigma_2^p$ 或 $\Pi_2^p$)。它们既不像在 $\mathsf{NP}$ 里那么”只需猜一个解”,又远没到 $\mathsf{PSPACE}$ 那么难——关键在于量词交替的层数是常数。

关于 $\mathsf{PH}$ 有一个反复出现、需要小心的现象:坍缩(collapse)。人们相信 $\mathsf{PH}$ 是一座”无限高”的塔,每一层都严格大于下一层($\Sigma_k^p\subsetneq\Sigma_{k+1}^p$ 对所有 $k$);但这从未被证明。反过来,有一条结构性的”刚性”定理:如果某两层相邻处发生重合,例如 $\Sigma_k^p=\Pi_k^p$(等价地 $\Sigma_k^p=\Sigma_{k+1}^p$),就能推出整座塔从那一层起全部坍平,即

\[\mathsf{PH}=\Sigma\_k^p.\]

直觉是:一旦第 $k$ 层对取补封闭,你就能把第 $k{+}1$ 层最外侧的量词”吸收”进第 $k$ 层里,归纳地把任意高的塔压回第 $k$ 层。特别地,若 $\mathsf{P}=\mathsf{NP}$,则取 $k=1$ 得 $\Sigma_1^p=\Pi_1^p$,于是 $\mathsf{PH}$ 直接坍缩到 $\mathsf{P}$;若 $\mathsf{NP}=\mathsf{co\text{-}NP}$,则 $\mathsf{PH}$ 坍缩到第一层 $\mathsf{NP}$。因此”$\mathsf{PH}$ 不坍缩”这一信念,比 $\mathsf{P}\neq\mathsf{NP}$ 还要强,它常被当作一种结构性公理来推断别的结论:很多论文形如”若某事成立,则 $\mathsf{PH}$ 坍缩;而 $\mathsf{PH}$ 坍缩被认为极不可能,故某事(很可能)不成立”。

PSPACE:换一种资源来度量

到目前为止我们度量的都是时间。如果改用空间(内存)来度量呢?$\mathsf{PSPACE}$ 是用多项式大小的内存(对运行时间不设限,只要它最终停机)能解决的所有问题。这里要小心区分两种资源:一个 $\mathsf{PSPACE}$ 算法允许跑指数长的时间,只要任一时刻占用的内存格子数被 $

$ 的多项式所界定。直观上,空间比时间”更可重复利用”,同一块内存可以被反复擦写,所以 $\mathsf{PSPACE}$ 是个相当宽广的类。

为什么 $\mathsf{PH}\subseteq\mathsf{PSPACE}$?给定一个第 $k$ 层的量词式 $\exists y_1\forall y_2\cdots V(x,\vec y)$,我们可以用多项式空间逐一枚举每个 $y_i$ 的所有取值并递归地求值:枚举一个 $y_i$ 只需存它当前的取值(多项式长度),求值 $V$ 也只需多项式空间;虽然总时间是指数级(要遍历指数多的赋值组合),但任一时刻在栈上的信息量是多项式的。于是整座 $\mathsf{PH}$ 都被装进了 $\mathsf{PSPACE}$。

$\mathsf{PSPACE}$ 的标准代表问题是量词布尔公式(quantified Boolean formula, QBF / TQBF):给定一个所有变量都被 $\exists$ 或 $\forall$ 量词约束、且量词可任意交替的布尔公式(例如 $\exists x_1\forall x_2\exists x_3\cdots\,\varphi(x_1,x_2,\dots)$),判断它是否为真。注意 QBF 与 $\mathsf{PH}$ 的关系:$\mathsf{PH}$ 的第 $k$ 层只允许固定的、常数个量词交替块,而 QBF 允许量词交替的次数随输入增长任意多(交替层数本身就是输入的一部分)。正是这”无界次交替”把问题从 $\mathsf{PH}$ 抬升到了 $\mathsf{PSPACE}$ 的顶点:QBF 是 $\mathsf{PSPACE}$ 完全($\mathsf{PSPACE}$-complete)问题。这一完全性结果可追溯到 Meyer 与 Stockmeyer 1973 年关于”需要指数空间/时间的字问题”的工作,并在随后被整理成标准形式。可以把 QBF 直观地读成一场”两人对弈”:$\exists$ 是想让公式为真的玩家,$\forall$ 是想让它为假的对手,他们轮流给变量赋值,问”$\exists$ 方是否有必胜策略”。

这里还藏着一个漂亮而反直觉的定理:Savitch 定理(Savitch, 1970)。它说明非确定的空间并不比确定的空间强多少:任何用 $S(n)\ge\log n$ 非确定空间能做的事,都能用 $O(S(n)^2)$ 确定空间完成,即

\[\mathsf{NSPACE}(S(n))\subseteq\mathsf{DSPACE}\big(O(S(n)^2)\big).\]

其证明思想是把”非确定计算能否从初始格局到达接受格局”化归为图上的可达性问题,再用一个分治式的递归”中点搜索”(REACH$(u,v,2^i)$ 询问能否在 $2^i$ 步内从 $u$ 到 $v$,通过枚举中点 $w$ 递归为 REACH$(u,w,2^{i-1})$ 与 REACH$(w,v,2^{i-1})$)来求解。这一递归的深度是 $O(S)$,每层只需存一个 $O(S)$ 大小的格局,故总空间 $O(S^2)$。一个直接推论是 $\mathsf{PSPACE}=\mathsf{NPSPACE}$:取 $S(n)$ 为多项式,平方后仍是多项式。换言之,在空间这个维度上,”非确定性”这个让 $\mathsf{P}$ 与 $\mathsf{NP}$ 之间产生鸿沟的东西,竟然几乎免费(只付出平方的代价)。这与时间维度的情形(我们连 $\mathsf{P}=\mathsf{NP}$ 都无法证否)形成鲜明对照,也提示我们:$\mathsf{P}$ 对 $\mathsf{NP}$ 之难,本质上是个关于”时间”的难题。

$\mathsf{PSPACE}$ 还有一张极具说服力的”博弈名片”。许多双人完全信息博弈的判定问题(给定局面,问先手是否有必胜策略)天然就是”我有一步走法,使得对所有对手回应,我都有走法,使得……”这样的无界量词交替,因此正落在 $\mathsf{PSPACE}$ 附近。把井字棋、围棋这类有限棋盘的游戏推广到 $n\times n$ 棋盘后,广义地理棋(generalized geography,在有向图上轮流移动且不可重访顶点,无法移动者负)是 $\mathsf{PSPACE}$ 完全的,这是最早被证明 $\mathsf{PSPACE}$ 完全的双人博弈之一(归约直接模拟 QBF 中存在/全称玩家的选点过程)。要注意一个微妙之处:只有当博弈的总步数被棋盘规模的多项式所限制时,它才落在 $\mathsf{PSPACE}$(地理棋因”不可重访”使局长被顶点数即多项式所界);一旦棋局可以持续指数长的步数,问题就会爬升到更高的 $\mathsf{EXP}$(见下)。这条”局长是否多项式有界”的分界线,正是 $\mathsf{PSPACE}$ 完全博弈与 $\mathsf{EXPTIME}$ 完全博弈的真正分水岭。

EXP / EXPTIME:第一道真鸿沟所在

$\mathsf{EXP}$(也写作 $\mathsf{EXPTIME}$)是用指数时间 $2^{n^{O(1)}}$(即对某个常数 $c$,时间界为 $2^{n^c}$)能解决的所有问题。它位于我们这条链的顶端:$\mathsf{PSPACE}\subseteq\mathsf{EXP}$(理由:一台只用多项式空间 $s(n)$ 的机器,在标准约定 $s(n)\ge\log n$ 下,其不同格局总数——综合内部状态、纸带内容与读写头位置等因素后——是 $2^{O(s(n))}$ 个,这里 $s(n)\ge\log n$ 保证了来自状态数与读写头位置的那些 $\mathrm{poly}(n)$ 因子可被吸收进 $2^{O(s(n))}$;若机器停机就必在这么多步内停机,否则会重复格局而陷入死循环,故时间也被指数所界)。

$\mathsf{EXP}$ 的特别之处在于,它是这条链上唯一与 $\mathsf{P}$ 之间已经被严格证明分开的大类。靠的是时间层级定理(time hierarchy theorem,Hartmanis 与 Stearns, 1965):粗略地说,给更多的时间,确实能解决严格更多的问题。其精确陈述是:若 $f,g$ 为”时间可构造”函数且 $f(n)\log f(n)=o(g(n))$,则 $\mathsf{DTIME}(f(n))\subsetneq\mathsf{DTIME}(g(n))$。证明用的是对角化(diagonalization):构造一台机器,模拟所有运行时间为 $f$ 的机器并在每个输入上”故意唱反调”,从而得到一个能在时间 $g$ 内判定、却不在 $\mathsf{DTIME}(f)$ 内的语言。把 $f$ 取为任意多项式、$g$ 取为某个指数函数,即得

\[\mathsf{P}\subsetneq\mathsf{EXP}.\]

这是这一整节里少数几个”$\subsetneq$”是真的严格而非猜测的地方之一。它带来一个意味深长的逻辑后果:既然 $\mathsf{P}\subsetneq\mathsf{EXP}$,而 $\mathsf{P},\mathsf{NP},\mathsf{PH},\mathsf{PSPACE},\mathsf{EXP}$ 形成一条包含链,那么这条链中至少有一处是严格的——我们确知”有真分隔存在”,却指不出它具体卡在哪两块之间。

$\mathsf{EXP}$ 也有自己的天然代表:那些”棋局可以拖到指数长”的广义博弈(此时不再有多项式的局长上界,$\mathsf{PSPACE}$ 的枚举论证失效)。把国际象棋推广到 $n\times n$ 棋盘后,Fraenkel 与 Lichtenstein 在 1981 年证明广义国际象棋是 EXPTIME 完全的;Robson 在 1983 年证明带基本劫(ko)规则的广义围棋同样是 $\mathsf{EXPTIME}$ 完全的,随后又证明广义西洋跳棋亦然。由于 $\mathsf{P}\subsetneq\mathsf{EXP}$ 是真分隔,而这些博弈是 $\mathsf{EXPTIME}$ 完全(即 $\mathsf{EXP}$ 中最难的一档),这些结果说明”为 $n\times n$ 国际象棋算出完美策略”在最坏情形下确实需要随 $n$ 指数增长的时间——这是少有的、能板上钉钉地说”这个问题真的难”的例子(对比之下,$\mathsf{NP}$ 完全问题的”难”仍依赖于尚未证明的 $\mathsf{P}\neq\mathsf{NP}$)。

#P:不再问”有没有”,而问”有多少”

前面所有的类问的都是判定性问题(decision problem):答案非”是”即”否”。但很多时候我们关心的是数量:不是”这个公式有没有满足赋值”,而是”它有多少个满足赋值”。这就引出了计数类 $#\mathsf{P}$(读作”sharp-P”),由 Leslie Valiant 在 1979 年的奠基性论文 The complexity of computing the permanent 中提出。注意一个范畴上的区别:$#\mathsf{P}$ 是一个函数类(其成员输出一个自然数),而非语言/判定类。

形式上,一个函数 $f:{0,1}^\ast\to\mathbb{N}$ 属于 $#\mathsf{P}$,若存在一台多项式时间非确定图灵机 $M$,使得对每个输入 $x$,$f(x)$ 恰好等于 $M$ 在 $x$ 上接受路径(accepting computation path)的条数。把这个定义与 $\mathsf{NP}$ 对照看尤其清楚:$\mathsf{NP}$ 问”是否存在至少一条接受路径”,$#\mathsf{P}$ 问”有几条接受路径”。因此 $\mathsf{NP}$ 里每个”自然”问题都有一个对应的 $#\mathsf{P}$ 计数版本:$\mathsf{NP}$ 问 SAT 是否有解,$#\mathsf{P}$ 则问 $#$SAT——一个公式到底有几个满足赋值。显然计数至少和判定一样难:若能数出满足赋值的个数,只需看它是否大于 $0$ 就解决了判定问题。

Valiant 同一篇论文还给出了 $#\mathsf{P}$ 最著名的代表问题:计算 $n\times n$ 矩阵 $A$ 的积和式(permanent)

\[\operatorname{perm}(A)=\sum\_{\sigma\in S\_n}\prod\_{i=1}^{n}A\_{i,\sigma(i)},\]

其中 $S_n$ 是全体排列。积和式的代数定义与行列式

\[\det(A)=\sum\_{\sigma\in S\_n}\operatorname{sgn}(\sigma)\prod\_{i=1}^{n}A\_{i,\sigma(i)}\]

几乎一模一样,只是去掉了那个符号因子 $\operatorname{sgn}(\sigma)$(那些恼人的正负号)。可正是这一点点改动,让它从”多项式时间可算”(行列式可用高斯消元求值,按域上算术运算计数为 $O(n^3)$;直觉上,消元之所以可行,依赖的是行列式作为列向量函数的多线性与交替性——正是这一对结构性质,让行交换只带来一个符号、行的线性组合不改变值,从而允许逐列消元,这一点应理解为启发式直觉而非完整论证;此外,在整数比特复杂度意义下还需用无分式的 Bareiss 消元以避免中间项膨胀)一跃成为 $#\mathsf{P}$ 完全($#\mathsf{P}$-complete),哪怕把矩阵元素限制成只有 $0$ 和 $1$ 也依然如此(此时 $\operatorname{perm}(A)$ 恰好计数二部图中完美匹配的个数)。这条”积和式 vs 行列式”的鸿沟,是复杂性理论中最优雅的对照之一:形式上近乎孪生的两个量,计算难度却天差地别。这里要点明 $#\mathsf{P}$ 完全的含义:$\operatorname{perm}$ 不仅在 $#\mathsf{P}$ 中,而且 $#\mathsf{P}$ 中任何函数都能在多项式时间内归约到它,所以它代表了整个计数类的难度上限。

$#\mathsf{P}$ 到底有多强?Seinosuke Toda 在 1991 年给出了一个令人震惊的答案,即 Toda 定理:

\[\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}.\]

这里 $\mathsf{P}^{#\mathsf{P}}$ 指”配备一个 $#\mathsf{P}$ 神谕的多项式时间”:你拥有一台能瞬间回答任意 $#\mathsf{P}$ 计数问题(例如”这个公式有多少个满足赋值”)的神谕,再配上普通的多项式时间计算。定理说,凭此你就能解决整座多项式层级里的所有问题——无论那座塔有多高、量词交替多少层。换句话说,一次计数神谕,就吞下了任意常数层的量词交替。这意味着”计数”这一种看似朴素的能力,其威力足以一举淹没存在/全称交替堆出来的全部层级,这是相当出人意料的:计数表面上只是 $\mathsf{NP}$ 的”加强版”,却凌驾于整座 $\mathsf{PH}$ 之上。这个结果深刻揭示了计数的力量,被公认为复杂性理论的里程碑,并为 Toda 赢得了 1998 年的哥德尔奖(Gödel Prize)。原始证明分两步走:第一步证明 $\mathsf{PH}$ 落在 $\mathsf{BPP}^{\oplus\mathsf{P}}$ 之中($\oplus\mathsf{P}$ 即”奇偶校验”类,问接受路径数的奇偶性),其中用到了 Valiant–Vazirani 定理(把一般可满足性随机地归约为”恰好唯一满足赋值”)的变体;第二步证明这个带随机化与奇偶校验的类被 $\mathsf{P}^{#\mathsf{P}}$ 吞没。一个清晰的现代证明可见 A Simple Proof of Toda’s Theorem。

顺带一提:随机类 BPP

我们度量过时间、空间,叠过量词,数过解的个数。还有一个维度值得一提:随机性(randomness)。$\mathsf{BPP}$(bounded-error probabilistic polynomial time)是那些存在多项式时间随机算法、且对任何输入都以高概率给出正确答案的问题类。精确地说,$L\in\mathsf{BPP}$ 当且仅当存在一个多项式时间随机算法 $A$,使得 $x\in L$ 时 $\Pr[A(x)=1]\ge 2/3$,$x\notin L$ 时 $\Pr[A(x)=1]\le 1/3$。这里”$2/3$”并不特殊:由于错误是双侧有界的,只要把算法独立重复多次取多数票,错误概率就会指数级下降(Chernoff 界),因此任何固定在 $1/2$ 与 $1$ 之间的常数门槛、甚至 $1/2+1/\mathrm{poly}(n)$ 的门槛,都给出同一个类。

一个引人入胜的开放问题是:随机性到底有没有给计算带来真正的额外能力?主流的猜想是没有,即

\[\mathsf{P}=\mathsf{BPP}.\]

这一信念有坚实的去随机化(derandomization)理论支撑——若存在足够强的、对指数规模电路也难以计算的布尔函数(电路下界),就能用伪随机生成器把随机算法确定化——但前提性的电路下界至今未被证明,故 $\mathsf{P}=\mathsf{BPP}$ 仍是猜想。已知的是 $\mathsf{BPP}$ 落在多项式层级的第二层之内,

\[\mathsf{BPP}\subseteq\Sigma\_2^p\cap\Pi\_2^p\]

(这是 Sipser–Gács–Lautemann 定理),所以它并未跳出我们这张地图;而 $\mathsf{BPP}$ 是否包含于 $\mathsf{NP}$ 仍是开放的。

整张地图与那些”未知的严格性”

把上面所有类拼在一起,得到本节开头那条公认的包含链:

\[\mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PH}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}.\]

现在要强调的是,这条链上几乎每一个 $\subseteq$ 都还不知道是不是真包含 $\subsetneq$:

$\mathsf{P}\subseteq\mathsf{NP}$:严格性未知(这正是那个百万美元问题)。
$\mathsf{NP}\subseteq\mathsf{PH}$:严格性未知;$\mathsf{NP}=\Sigma_1^p$ 是 $\mathsf{PH}$ 的第一层,若相等(即 $\mathsf{NP}=\mathsf{PH}$),则 $\mathsf{PH}$ 坍缩到第一层。
$\mathsf{PH}\subseteq\mathsf{PSPACE}$:严格性未知;人们普遍相信严格,但若 $\mathsf{PH}=\mathsf{PSPACE}$,则因 $\mathsf{PSPACE}$ 有完全问题(QBF)而 $\mathsf{PH}$ 被广泛相信没有完全问题,会推出 $\mathsf{PH}$ 坍缩,因此被认为极不可能。
$\mathsf{PSPACE}\subseteq\mathsf{EXP}$:严格性未知。
而 $\mathsf{P}\subseteq\mathsf{EXP}$:严格,这是被证明了的,由时间层级定理给出 $\mathsf{P}\subsetneq\mathsf{EXP}$。

最后那一行是关键:整条链首尾两端 $\mathsf{P}$ 与 $\mathsf{EXP}$ 已被确知分开,所以中间这一串 $\subseteq$ 至少有一处必定是严格的,只是没有人知道究竟卡在哪里。值得补一句:即便是相隔更近的 $\mathsf{NP}\subseteq\mathsf{PSPACE}$、$\mathsf{NP}\subseteq\mathsf{EXP}$ 这类包含,严格性也同样未知;我们手里唯一确凿的”真分隔”几乎都来自层级定理那种基于对角化的论证,而对角化恰恰对带神谕的世界”看不穿”(存在神谕使 $\mathsf{P}=\mathsf{NP}$、也存在神谕使 $\mathsf{P}\neq\mathsf{NP}$),这正是 $\mathsf{P}$ 对 $\mathsf{NP}$ 难以攻破的深层障碍之一。这幅图景恰如其分地概括了计算复杂性理论的现状:我们能把地图画得很大、很精细,能在上面标出无数地标($\mathsf{PSPACE}$ 完全的博弈、$#\mathsf{P}$ 完全的积和式、坍缩与 Toda 定理这样的深刻结构),却仍然无法在大多数相邻大陆之间,确凿地划出那道分界线。

参考与延伸阅读:Stockmeyer 关于多项式层级的原始论文 The polynomial-time hierarchy (1976);Valiant 关于积和式与 $#\mathsf{P}$ 的奠基论文 The complexity of computing the permanent (1979);Toda 定理的简明证明见 A Simple Proof of Toda’s Theorem;广义国际象棋的 $\mathsf{EXPTIME}$ 完全性见 Fraenkel–Lichtenstein (1981)。此外,本节涉及的其余具名结果及其原始出处依次为:Savitch 定理(W. J. Savitch, 1970)、时间层级定理(J. Hartmanis 与 R. E. Stearns, 1965)、QBF/TQBF 的 $\mathsf{PSPACE}$ 完全性(可追溯到 A. R. Meyer 与 L. J. Stockmeyer, 1973,并由 L. J. Stockmeyer 整理为标准形式)、$\mathsf{BPP}\subseteq\Sigma_2^p\cap\Pi_2^p$(Sipser–Gács–Lautemann 定理)、广义围棋的 $\mathsf{EXPTIME}$ 完全性(J. M. Robson, 1983),以及关于相对化障碍的神谕分隔结果(Baker–Gill–Solovay, 1975)。

全函数问题与 PPAD 一家：TFNP、PPAD、PPA、PPP、PLS、CLS

到目前为止，我们的复杂度版图基本被两类问题占据：要么是判定问题（decision problem，回答”是/否”），要么是 $\mathsf{NP}$ 这种”解未必存在、但一旦给出可快速验证”的搜索问题。然而现实中有一大批问题具有一种特殊的结构：解一定存在，数学定理已经先验地保证了这一点，难的不是”有没有解”，而是”怎么把那个一定存在的解找出来”。纳什均衡（Nash equilibrium）就是典型例子：纳什（John Nash）1951 年的定理保证任何有限博弈都有混合策略均衡，所以”存不存在均衡”这个判定问题是平凡的（答案恒为”是”），但把那个均衡算出来却出奇地困难。这类问题的难度无法被 P/NP 的二分法捕捉，需要一套专门的复杂度类来刻画，这就是本节的主角 $\mathsf{TFNP}$ 及其下属的 PPAD 一家。

读者可以先建立一个总的直觉：判定问题问”是否存在”，$\mathsf{NP}$ 搜索问题问”如果存在，请找出来”，而 $\mathsf{TFNP}$ 问题问的是”它一定存在，请找出来”。第三种问法把”存在性”从答案里抽走了，于是难度被纯粹地压在”构造”这件事上——这正是这一族复杂度类要量度的对象。

一、TFNP：为什么”解一定存在”需要一套新房子

先把”搜索问题”形式化。一个 NP 搜索问题（NP search problem） 由一个多项式时间可判定的二元关系 $R(x,y)$ 与一个多项式界 $p$ 给出：对输入 $x$，合法的解是满足 $

\le p(

)$ 且 $R(x,y)=1$ 的 $y$；任务是”给定 $x$，输出一个这样的 $y$，若不存在则报告无解”。这里有两个关键约束：解的长度被多项式限制（否则验证无从谈起），以及给定候选解能在多项式时间内验证（这正是 $\mathsf{NP}$ 里那个”易验证”条件的搜索版本）。

TFNP（Total Function NP，全函数 NP） 就是上述搜索问题中全（total）的那一部分。完整地说，一个关系 $R$ 属于 $\mathsf{TFNP}$，当且仅当它同时满足三个条件：(i) $R$ 是 $\mathsf{P}$ 中可判定的关系（语法约束，保证候选解易验证）；(ii) 存在多项式界 $p$ 限制解的长度；(iii) 对每一个输入都有解（全性）。形式上：

\[R\in\mathsf{TFNP}\quad\Longleftrightarrow\quad \underbrace{R\in\mathsf{P}}_{\text{(i) 可判定}}\ \wedge\ \underbrace{\forall x\;\exists y\;\big(|y|\le p(|x|)\ \wedge\ R(x,y)=1\big)}_{\text{(ii) 多项式界 + (iii) 全性}}.\]

必须把 (i) 这条语法约束写进定义本体，而不能仅当作事后补充：如果只保留全性那个量词式，那么任意”对每个输入都有解”的关系（哪怕完全不可计算）都会满足它，类就太大了。真正使 $\mathsf{TFNP}$ 区别于一般 $\mathsf{NP}$ 搜索问题（后者允许某些 $x$ 无解）的，是把易验证与全性（totality）这两个条件同时焊在一起。

一个自然的问题是：既然 $\mathsf{TFNP}$ 看起来只是 $\mathsf{NP}$ 搜索问题的一个子集，为什么不能直接用 $\mathsf{P}$ 和 $\mathsf{NP}$-complete 这两个已有的标签来分类它？答案揭示了 $\mathsf{TFNP}$ 最深刻的性质。

关键结论来自 Megiddo（梅吉多）与 Papadimitriou（帕帕迪米特里欧）1991 年的工作 On total functions, existence theorems and computational complexity：如果 $\mathsf{TFNP}$ 中存在某个 $\mathsf{NP}$-hard 问题，那么 $\mathsf{NP}=\mathsf{co\text{-}NP}$（多项式层级随之坍缩到第一层）。这里”$\mathsf{TFNP}$ 中某问题是 $\mathsf{NP}$-hard 的”需稍作澄清：它指的是某个 $\mathsf{TFNP}$ 搜索问题在多项式时间 Cook（Turing）归约意义下足以求解一个 $\mathsf{NP}$-complete 的判定问题。

这个结论的直觉值得细品。设想我们想把一个 $\mathsf{NP}$-hard 的判定问题（比如 SAT）归约到某个全函数问题 $R$ 上：归约要用”是否找到解”来编码”原 SAT 实例是否可满足”。但全函数问题永远有解——无论原实例可满足与否，归约出的 $R$-实例都必然返回一个解。于是”找到了解”这个事件不再携带任何信息，它对所有输入都发生。要让归约有意义，你必须能用解本身的内容去见证一个否定回答（即”不可满足”），也就是说，那个总能拿到的解 $y$ 里必须编码着一个可在多项式时间内验证的”不可满足证书”。但”不可满足”正是 co-NP 类问题，为它提供多项式可验证的证据恰好就推出了 $\mathsf{NP}=\mathsf{co\text{-}NP}$。由于学界普遍不相信多项式层级会坍缩，$\mathsf{TFNP}$ 中的问题被认为既不太可能落在 $\mathsf{P}$ 中（否则就不必大费周章），又不太可能是 $\mathsf{NP}$-hard 的，它们卡在 $\mathsf{P}$ 与 $\mathsf{NP}$ 之间的”中间地带”。这是一种条件性的难度证据：我们无法证明它们不在 $\mathsf{P}$ 中，但能证明它们若是 $\mathsf{NP}$-hard 就会引发灾难性后果。

更微妙的是，$\mathsf{TFNP}$ 是一个语义定义（semantically defined）的类：它的成员资格依赖于”对所有输入都有解”这个全局条件，而这个条件无法在语法上直接检查——给定一段判定 $R$ 的代码，没有算法能机械地判断它是否处处有解（这本身是不可判定的）。一个直接后果是：$\mathsf{TFNP}$ 本身一般不被认为拥有自然/语法刻画下的完全问题（complete problem），而它究竟有没有完全问题，本身仍是一个公开问题。粗略地说，要谈一个类的完全问题，通常需要这个类能被一种”语法模板”统一刻画，使得”枚举该类全体成员”成为可能；而语义类缺乏这样的枚举，于是难以拥有自然的完全问题。

这正是需要一套子类的根本原因：人们转而定义若干语法定义（syntactically defined）的子类，每个子类都把全性”焊死”在某个具体的存在性论证（existence argument）上。这里的设计哲学是：选定一条数学上的存在性定理（如握手引理、鸽巢原理、单调下降必停），把问题的输入限定为”恰好满足该定理前提”的电路编码，那么全性就由该定理自动成立、无需额外检查，于是这些子类天然是语法的、天然带有完全问题。下面这”一家子”就是按论证原理来划分的——每个类对应一种”非构造性存在性证明”，而该类的完全问题就是”把这个证明所保证的对象找出来”。

二、PPAD：有向图奇偶性论证与 End-of-the-Line

PPAD（Polynomial Parity Argument, Directed，多项式奇偶论证·有向版） 由 Papadimitriou 在 1994 年的奠基论文 On the complexity of the parity argument and other inefficient proofs of existence（JCSS 卷 48, pp. 498–532，DOI 10.1016/S0022-0000(05)80063-7）中引入。它由一个完全问题 End-of-the-Line（线之尽头） 定义。

End-of-the-Line 的设定是：给定一个指数级大的有向图，顶点集为 ${0,1}^n$（即 $2^n$ 个顶点），每个顶点的入度和出度都至多为 1。这个度数约束极为关键：它使得整张图必然分解为若干条简单有向路径和简单有向环的不相交并（因为没有顶点能有两条出边或两条入边，所以不会出现分叉或汇合）。这张图不是显式给出（它指数级大，写不下），而是通过两个多项式规模的电路 $P$（predecessor，前驱）与 $S$（successor，后继）隐式压缩表示：电路输入一个顶点编号，输出它声称的前驱和后继。我们用一个自洽性约定来定义边：存在从 $u$ 到 $v$ 的边，当且仅当 $S(u)=v$ 且 $P(v)=u$。已知存在一个标准源点（source），习惯上取顶点 $0^n$，它出度为 1、入度为 0（即 $P(0^n)=0^n$ 而 $S(0^n)\ne 0^n$）。要求是：找出另一个入度与出度之和为 1 的顶点，也就是另一个源点（入度 0、出度 1）或一个汇点（sink，出度 0、入度 1，即某条路径的终点）。这里”度数为 1”专指有向图中入度与出度之和等于 1，请与后文 $\mathsf{PPA}$ 无向图里的”度数”（边的根数）区分开，以免记号漂移。

它的全性论证就是一句朴素的奇偶性观察：在这种入度、出度均不超过 1 的有向图中，入度与出度之和为奇数（在此即恰为 1）的顶点必然成对出现。理由是：每条简单路径恰好贡献两个这样的端点（一个源、一个汇），而每条环不贡献任何这样的顶点。于是入出度之和为 1 的顶点总数是偶数。题目白送了一个这样的顶点（标准源点 $0^n$），它所在那条路径的另一端就必然存在，且也是一个入出度之和为 1 的顶点——这就是要找的解。这个”有向图入出度奇偶性”的平凡论证，构成了 $\mathsf{PPAD}$ 全部存在性保证的核心。$\mathsf{PPAD}$ 定义为所有可多项式时间（多对一/Karp 式）归约到 End-of-the-Line 的全函数搜索问题组成的类。

这里有一个常见的坑值得点明：End-of-the-Line 之所以难，不是因为路径不存在（它一定存在），而是因为这条路径可能指数级长，你不能简单地”从源点一步步走到底”——那要走指数多步。隐式电路表示让你能局部地问”下一个是谁”，却不让你免费地全局俯瞰整张图，这正是 $\mathsf{PPAD}$ 难度的来源。

与 Sperner 引理、Brouwer 不动点定理的内在联系，是 $\mathsf{PPAD}$ 真正深刻之处。Papadimitriou 在同一篇论文中证明了三维 Sperner 问题（Sperner 染色组合引理对应的”找全色单纯形”问题）以及 Brouwer 不动点（布劳威尔不动点） 的离散逼近问题都是 PPAD-complete（PPAD 完全） 的，并把来自数理经济学的交换均衡（exchange equilibrium） 问题纳入了 $\mathsf{PPAD}$。其内在机制是：Sperner 引理的标准（构造性）证明本身就是在构造一条”找全色单纯形”的路径——把每个小单纯形看成顶点，沿”共享某种特定染色面”的相邻关系前进，可以验证每个单纯形至多有一条进边、一条出边，这恰好就是 End-of-the-Line 的入出度结构；路径的起点由边界上的奇偶性强制存在，而路径的终点就是要找的全色单纯形。而 Sperner 引理又是 Brouwer 不动点定理的组合化身（通过单纯形剖分取极限即得连续版的不动点）。换句话说，Brouwer 不动点定理”解一定存在但难以构造”这件事，其计算本质就是 $\mathsf{PPAD}$。这条线索后来由 Daskalakis、Goldberg、Papadimitriou 等人推到顶峰，证明了计算纳什均衡是 PPAD-complete 的：一般博弈（任意人数）的情形由 Daskalakis–Goldberg–Papadimitriou 给出（STOC 2006，期刊版载 SICOMP），两人博弈的情形随后由 Chen–Deng 在 Settling the Complexity of Two-Player Nash Equilibrium（FOCS 2006）中给出。这从计算复杂度上解释了为什么纳什均衡虽然总存在却难以求解。我们将在下一节专门展开这一结果。

三、兄弟类：PPA、PPP、PLS

$\mathsf{PPAD}$ 有几个建立在不同存在性原理之上的”兄弟”，它们共同构成 $\mathsf{TFNP}$ 的语法子类家族。理解它们的最好方式，是看清各自焊死的是哪一条存在性定理。

PPA（Polynomial Parity Argument，无向版）。如果说 $\mathsf{PPAD}$ 来自有向图的奇偶论证，$\mathsf{PPA}$ 来自无向图的奇偶论证，依据的原理是握手引理：在任何无向图中，奇度顶点的个数必为偶数（因为所有顶点度数之和等于边数的两倍，是偶数）。$\mathsf{PPA}$ 的完全问题 Leaf（叶子）的设定与 End-of-the-Line 平行：给定一个隐式表示的、每个顶点度数至多为 2 的无向图（于是它是若干条路径与环的并），并给定一个已知的奇度顶点（在度 $\le 2$ 的约束下，奇度顶点只能是度恰为 1 的”叶子”），要求找出另一个奇度顶点。注意此处的”度数”指无向图中一个顶点所关联的边数，与 $\mathsf{PPAD}$ 那里”入度+出度”的有向意义不同。由于无向论证比有向论证更宽松——任何有向 End-of-the-Line 实例只要”忘掉”边的方向，就变成一个合法的无向实例，而原来的源点/汇点都成为度为 1 的奇度顶点——所以 $\mathsf{PPAD}\subseteq\mathsf{PPA}$。$\mathsf{PPA}$ 捕捉了一批带”对称性 / 无方向”色彩的存在性定理，典型的 PPA-complete 问题包括项链分割（necklace splitting）、火腿三明治定理（ham sandwich theorem） 的离散版本，以及与 Borsuk–Ulam 定理相关的问题——这些定理的证明都依赖某种”对称配对”而非有向流动，因而落在 $\mathsf{PPA}$ 而非 $\mathsf{PPAD}$。

PPP（Polynomial Pigeonhole Principle，多项式鸽巢原理）。Papadimitriou 在引入 $\mathsf{PPAD}$、$\mathsf{PPA}$ 的同一篇 1994 年论文中也引入了 $\mathsf{PPP}$。它的全性论证是鸽巢原理：其完全问题 Pigeon 给定一个电路 $C:{0,1}^n\to{0,1}^n$，要求要么找到一个被映到指定”溢出值”（习惯上取 $0^n$）的元素，即满足 $C(x)=0^n$ 的 $x$，要么找到两个不同元素 $u\ne v$ 使 $C(u)=C(v)$（即一对碰撞 collision）。全性来自鸽巢原理：如果没有任何元素映到 $0^n$，那么 $C$ 实际上把 $2^n$ 个元素映进 $2^n-1$ 个像里（去掉了 $0^n$ 这个”鸽巢”），碰撞必然存在。可以证明 $\mathsf{PPAD}\subseteq\mathsf{PPP}$（End-of-the-Line 的后继结构能被编码成一个鸽巢式映射）。$\mathsf{PPP}$ 与密码学联系紧密，因为寻找哈希碰撞本质上就是一个鸽巢式的全函数问题；长期以来 $\mathsf{PPP}$ 缺乏 Pigeon 之外的”自然”完全问题，直到近年 Sotiraki、Zampetakis、Zirdelis 在 PPP-Completeness with Connections to Cryptography 中给出了 $\mathsf{PPP}$ 的首个自然完全问题（与格密码中的同余问题相关）。

PLS（Polynomial Local Search，多项式局部搜索）。这是这一家中最早出现的成员，由 Johnson（约翰逊）、Papadimitriou、Yannakakis（亚纳卡基斯）在 1988 年的论文 How easy is local search?（JCSS 卷 37，会议版见 1985 FOCS）中定义。它的存在性论证不是奇偶或鸽巢，而是局部最优一定存在这一单调性事实。形式化地，一个 PLS 问题给定三样东西：一个能在多项式时间内识别合法解的有限解空间（每个解是一个长度多项式有界的串）、一个多项式时间可计算的目标（势）函数 $\Phi$（把解映到一个有界整数），以及一个多项式时间可计算的邻域函数 $N$（给定一个解，要么返回一个目标值严格更优的邻居，要么宣布”我是局部最优”）。要求是找出一个局部最优解（local optimum），即 $N$ 在其上宣布停止的解。全性论证是：从任意解出发，不断调用 $N$ 走向严格更优的邻居，由于势函数取值在一个有限整数集中且单调严格改善，这个过程不可能无限进行，必然在有限步内停在某个局部最优解处。注意这只保证局部最优存在，而那条改善路径可能指数级长——这正是 $\mathsf{PLS}$ 难度的根源，与 End-of-the-Line 里”路径很长”如出一辙。$\mathsf{PLS}$ 的全性来自势函数有界这一单调性论证，与图奇偶论证是不同的来源。经典的 PLS-complete 问题包括用 Kernighan–Lin 邻域求 Max-Cut 局部最优、求解某些拥塞博弈（congestion game） 的纯策略均衡等。$\mathsf{PLS}$ 同样夹在 $\mathsf{P}$ 与 $\mathsf{NP}$ 之间：如果 $\mathsf{PLS}$ 中某问题是 $\mathsf{NP}$-hard 的，同样会推出 $\mathsf{NP}=\mathsf{co\text{-}NP}$（与 Megiddo–Papadimitriou 论证同理，因为 $\mathsf{PLS}\subseteq\mathsf{TFNP}$）。

需要强调的是，奇偶论证（$\mathsf{PPAD}/\mathsf{PPA}$）与局部搜索论证（$\mathsf{PLS}$）是两套互不包含的存在性原理。在相对化（oracle，谕示）意义下，这些类彼此分离的格局现已基本厘清：Beame、Cook、Edmonds、Impagliazzo、Pitassi 在 1998 年给出了 $\mathsf{PPA}$、$\mathsf{PPAD}$、$\mathsf{PPADS}$、$\mathsf{PPP}$ 之间的谕示分离；近期 Göös、Hollender 等在 Separations in Proof Complexity and TFNP（FOCS 2022）中补全了 [JPY88]、[Pap94] 五个原始类之间最后悬而未决的谕示分离，例如在某谕示下 $\mathsf{PLS}\not\subseteq\mathsf{PPP}$。所谓”谕示分离”是说：存在一个谕示（oracle）$\mathcal{O}$，使得相对于 $\mathcal{O}$ 两个类不相等。这是当前技术下能给出的最强分离证据——它意味着任何”相对化”的证明手法都无法把这两个类等同起来。换言之，在我们当前的认知里，PPAD 一家成员确实被相信是不同的类，而非同一个类的不同名字（尽管它们在非相对化意义下的严格不等仍是未证实的猜想）。

四、CLS：两条论证线索的交汇及其惊人坍缩

人们很快注意到，有一批重要问题同时可以用奇偶/不动点论证（属于 $\mathsf{PPAD}$）和局部搜索论证（属于 $\mathsf{PLS}$）来保证有解，也就是落在 $\mathsf{PPAD}\cap\mathsf{PLS}$ 中。典型代表是：求解 P-矩阵线性互补问题（P-matrix LCP）、简单随机博弈（simple stochastic game）、寻找压缩映射（contraction map）的近似不动点、求多元多项式的近似驻点、求拥塞博弈的近似混合均衡等。这些问题既有不动点结构（让它们落入 $\mathsf{PPAD}$），又有势函数结构（让它们落入 $\mathsf{PLS}$），却长期没人找到多项式算法，于是成为 $\mathsf{PPAD}\cap\mathsf{PLS}$ 的天然居民。

为捕捉这种”连续域上、既有不动点又有势函数下降”的良性局部优化，Daskalakis（达斯卡拉基斯）与 Papadimitriou 在 2011 年的 Continuous Local Search（SODA 2011）中引入了 CLS（Continuous Local Search，连续局部搜索）。$\mathsf{CLS}$ 是一个语法定义的子类，被设计成 $\mathsf{PPAD}\cap\mathsf{PLS}$ 的一个更”自然、更紧”的内核：它要求在一个连续域（典型地取 $[0,1]^d$）上最小化一个多项式时间可计算、Lipschitz 连续的势函数 $\Phi$，并配有一个多项式时间可计算的连续改进函数，目标是找出一个近似的”局部最小”点。由构造立刻可知 $\mathsf{CLS}\subseteq\mathsf{PPAD}\cap\mathsf{PLS}$——连续不动点结构给出 $\mathsf{PPAD}$ 上界，势函数下降结构给出 $\mathsf{PLS}$ 上界。而 Daskalakis 与 Papadimitriou 当初猜想这个包含是严格的，即 $\mathsf{CLS}$ 应当比交集 $\mathsf{PPAD}\cap\mathsf{PLS}$ 更小，理由是连续性、Lipschitz 等额外要求看上去给问题加了”良性”约束。

这个猜想在十年后被推翻。Fearnley（费恩利）、Goldberg（戈德堡）、Hollender（霍兰德）、Savani（萨瓦尼）在 2021 年的 STOC 论文 The Complexity of Gradient Descent: CLS = PPAD ∩ PLS（后发表于 JACM 2023）中证明了 $\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}$。其核心技术贡献是：在有界域 $[0,1]^2$ 上对一个连续可微函数寻找 KKT 点（Karush–Kuhn–Tucker 点）——即满足约束优化一阶必要条件的点，直观上就是梯度下降会卡住、再也无法在可行域内继续下降的点——这一问题是 $\mathsf{PPAD}\cap\mathsf{PLS}$-complete 的，这是该交集类的第一个非人造（non-artificial）的完全问题。其标题”梯度下降的复杂度”点明了一个优美的刻画：把”在有界域上寻找梯度下降不动点（即 KKT 点）”这一问题形式化后，其复杂度恰好就是 $\mathsf{PPAD}\cap\mathsf{PLS}$-complete。需要强调，这里目标函数并不要求是凸的——凸情形通常是可解的，硬度恰恰来自非凸的实例。于是 $\mathsf{CLS}$ 不再是一个更小的内核，而正好等于这个交集；当初被认为”自然但更弱”的类，被证明拥有交集类的全部表达力。这是 TFNP 理论中少有的”反直觉坍缩”结果——人们本以为加了连续性约束会变弱，结果发现连续性恰好把两条论证线索缝合到了一起。

五、小结：P 与 NP 之间的精细地貌

把这一家子放在一起，可以画出大致的版图：所有这些类都满足 $\mathsf{P}\subseteq(\text{该类})\subseteq\mathsf{TFNP}$，并因 Megiddo–Papadimitriou 定理而一般不被认为是 $\mathsf{NP}$-hard 的。它们按存在性论证原理分层：

$\mathsf{PLS}$ 来自局部最优一定存在（势函数有界且单调严格下降）；
$\mathsf{PPAD}$ 来自有向图奇偶（即 Brouwer/Sperner 不动点）；
$\mathsf{PPA}$ 来自无向图奇偶（握手引理）；
$\mathsf{PPP}$ 来自鸽巢原理。

已知的包含关系是 $\mathsf{PPAD}\subseteq\mathsf{PPA}$、$\mathsf{PPAD}\subseteq\mathsf{PPP}$（两者都因 $\mathsf{PPAD}$ 的有向奇偶结构可被无向奇偶/鸽巢结构模拟），而 $\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}$ 精确地坐落在两条论证线索的接缝上。需要再次提醒：除这些已证的包含外，五个原始类之间的其余分离目前只有谕示意义下的证据（Beame 等 1998、Göös–Hollender 等 2022），它们彼此严格不等仍是未证实的猜想，只是被广泛相信。这一族类共同填补了”解一定存在却难以找到”这一被经典 P/NP 二分法忽略的灰色地带，并通过纳什均衡、市场均衡、不动点、梯度下降等问题，把抽象的复杂度理论与博弈论、经济学和连续优化牢牢绑定在一起，这也是为什么 PPAD 一家被视为算法博弈论（algorithmic game theory）的复杂度基石。

博弈论里的复杂度结论：Nash、市场均衡、相关均衡

算法博弈论（algorithmic game theory）有一个贯穿始终的张力：均衡存在与均衡可计算是两回事。John Nash 在 1950 年用不动点定理证明了：任何有限博弈都存在（混合策略）Nash 均衡。（更精确地说，Nash 在 1950 年的 PNAS 短文里用的是 Kakutani 不动点定理（Kakutani fixed-point theorem），而 1951 年发表于 Annals 的论文改用了 Brouwer 不动点定理（Brouwer fixed-point theorem）；本节后文按 Brouwer 版本展开，因为离散化最自然。）这是一条纯粹的存在性结论，它告诉你”解一定在那里”，却完全不告诉你”如何高效找到它”。整整半个多世纪之后，人们才把后一个问题的复杂度彻底钉死。本节就来梳理这一组结论，并解释为什么它们落在 $\mathsf{NP}$ 之外、需要一套专门的”全函数搜索”复杂度类来刻画。

在进入正题前，先把博弈论的几个基本对象就地说清，避免读者把”均衡”当成一个含义模糊的口号。一个有限正规型博弈（finite normal-form game）由以下数据给出：玩家集合 ${1,\dots,n}$；每个玩家 $i$ 有一个有限的纯策略集合 $S_i$；以及收益函数 $u_i:\prod_j S_j\to\mathbb{Q}$，把所有玩家的纯策略组合（称为一个策略组合 strategy profile）映到玩家 $i$ 的收益。一个混合策略（mixed strategy）是玩家在自己纯策略集合 $S_i$ 上的一个概率分布 $x_i\in\Delta(S_i)$。给定一组混合策略 $x=(x_1,\dots,x_n)$，玩家 $i$ 的期望收益记作 $u_i(x)$。所谓 Nash 均衡，就是一个混合策略组合 $x^*$，使得没有任何玩家能通过单方面改变自己的策略来严格提高期望收益：对每个玩家 $i$ 以及每个混合策略 $x_i’\in\Delta(S_i)$，都有 $u_i(x_i’,x^*{-i})\le u_i(x^*)$，其中 $x{-i}$ 表示除 $i$ 以外所有玩家的策略。这里 $x_i’$ 取遍整个单纯形 $\Delta(S_i)$；由期望收益对 $x_i’$ 的线性性，这等价于只对所有纯策略偏离做检验，二者完全一致。”双矩阵博弈”（bimatrix game）就是 $n=2$ 的特例，两个玩家的收益分别由两个矩阵 $A,B$ 给出，因而得名。Nash 的定理断言：上述 $x^*$ 永远存在，但它的坐标可能是无理数（一旦玩家数 $\ge 3$，Nash 本人就用一个三人扑克博弈给出了只有无理数均衡的例子），这一点后面会反复用到。

为什么 Nash 不像经典 NP 问题：全函数搜索与 PPAD

先看一个微妙之处。把”求 Nash 均衡”硬塞进判定问题（decision problem）的框架，会立刻失效。判定型问题”这个博弈是否存在 Nash 均衡”是平凡的：由 Nash 定理，答案永远是”是”。一个答案恒为”是”的判定问题不含任何信息，自然谈不上难。所以 Nash 均衡问题在本质上不是一个判定问题，而是一个搜索问题（search problem）：给定博弈，要求输出一个具体的均衡（或在近似版本里，输出一个近似均衡）。而且它是一个全函数（total）搜索问题——这里”全”指的是对每一个合法输入，解都保证存在（由 Nash 定理）。这与一般的 $\mathsf{NP}$ 搜索问题不同：例如”找一个使布尔公式为真的赋值”，对不可满足的公式根本无解。

这类”解保证存在、且解可在多项式时间内验证”的搜索问题，构成复杂度类 $\mathsf{TFNP}$（Total Function NP）。$\mathsf{TFNP}$ 处境尴尬的地方在于：它里面的问题不太可能是 $\mathsf{NP}$-complete。直觉是这样：$\mathsf{NP}$-hardness 的标准证明手段是从某个 $\mathsf{NP}$-complete 判定问题（比如 SAT）做归约，把”是/否”两种答案分别对应到搜索问题”有解/无解”上。但全函数搜索问题永远有解，那个”无解”分支根本不存在，归约无从落地。更精确地说，可以证明：如果某个 $\mathsf{TFNP}$ 问题在 Cook 归约（Cook / Turing reduction，即把一个 $\mathsf{NP}$-complete 判定问题用作子程序多项式时间归约到该问题）意义下是 $\mathsf{NP}$-hard，就会推出 $\mathsf{NP}=\mathsf{co\text{-}NP}$——这是一个被学界普遍怀疑为假的坍缩。这条”用不上力”的核心论断由 Megiddo 与 Papadimitriou 给出（On total functions, existence theorems and computational complexity, Theoretical Computer Science 1991）。所以经典的 $\mathsf{NP}$-hardness 框架在这里”用不上力”，刻画 $\mathsf{TFNP}$ 内部的难度需要更精细的工具。这正是要为 Nash 单独发明一个复杂度类的根本原因：它”难”，但不是 $\mathsf{NP}$ 那种难。

Christos Papadimitriou 在 1994 年（论文 On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence, JCSS）提出了一组刻画 $\mathsf{TFNP}$ 子结构的复杂度类，其分类原则极富洞见：把这些问题按照”保证解存在的那条非构造性组合论证”来归类。同一条存在性论证（不动点、奇偶论证、鸽巢、势函数下降……）背后往往藏着同一种计算难度。其中与博弈论关系最深的就是 $\mathsf{PPAD}$（Polynomial Parity Argument on Directed graphs，有向图上的多项式奇偶论证）。

$\mathsf{PPAD}$ 的典范完全问题是 END-OF-LINE：给定一张顶点数为 $2^n$ 的指数级大有向图，但这张图不是显式给出的，而是由两个多项式规模的电路 $S$（successor，后继）与 $P$（predecessor，前驱）简洁描述——对任一顶点 $v$，电路告诉你它的（至多一个）出邻居与（至多一个）入邻居。这些电路保证图中每个顶点的入度与出度都至多为 $1$，于是整张图分解为若干条简单路径与圈。已知某个标准顶点（例如全 $0$ 串）是一个入度为 $0$、出度为 $1$ 的源点（source）；要求找出另一个不平衡的顶点（unbalanced vertex，即入度 $\ne$ 出度的顶点）——也就是另一个源点，或者一个入度为 $1$、出度为 $0$ 的汇点（sink）。这样的顶点必然存在，因为一条有向简单路径恰有两个端点（这是有向图版本的奇偶论证；注意在这个入度/出度 $\le 1$ 的设定里，”端点”的正确不变量是入度 $\ne$ 出度，而不是无向图里”度为奇数”那套说法——后者对应的是另一个类 $\mathsf{PPA}$）。$\mathsf{PPAD}$ 正是所有可多项式时间归约到 END-OF-LINE 的 $\mathsf{TFNP}$ 问题之集合。

Brouwer 不动点的计算之所以落在 $\mathsf{PPAD}$ 里，是因为保证不动点存在的那套组合论证恰好对应 END-OF-LINE 的奇偶论证。其离散化版本是 Sperner 引理（Sperner’s lemma）：把一个单纯形（如三角形）做足够细的单纯形剖分，并对顶点做满足边界约束的三染色，则必存在一个”全色”的小单纯形（三个顶点颜色互异）；而寻找这个全色单纯形的算法正是沿着一条由染色规则定义的”路径”行走，这条路径的结构与 END-OF-LINE 一模一样。Nash 均衡的存在性证明用的正是 Brouwer 不动点（构造一个把策略组合映到策略组合的连续映射，其不动点即为均衡），于是 Nash 计算问题天然地”住”在 $\mathsf{PPAD}$ 里——这给出了 Nash 计算的上界。这就是 $\mathsf{PPAD}$ 这个类与 Nash 之间的根本联系。

核心定理之一：计算 Nash 均衡是 PPAD-complete

把 Nash 归到 $\mathsf{PPAD}$ 里只是上界，说明它”不会更难”。真正深刻的难度结论是它的下界，即 $\mathsf{PPAD}$-hardness：要把 END-OF-LINE（乃至任意 $\mathsf{PPAD}$ 问题）反过来归约到 Nash 计算，这等于把一个抽象的奇偶论证”编码”进一个具体博弈的收益结构里，技术上极为精巧。这条线由 Constantinos Daskalakis、Paul Goldberg 与 Christos Papadimitriou 完成：他们先证明了多人（最初是四人及以上）博弈中计算 Nash 均衡是 $\mathsf{PPAD}$-complete，发表于 STOC 2006，期刊版为 The Complexity of Computing a Nash Equilibrium, SIAM J. Comput. 2009。随后人数被进一步降到三人（Daskalakis 与 Papadimitriou 的后续工作）。

而最干净、也最令人意外的两人情形，由 Xi Chen 与 Xiaotie Deng 在 FOCS 2006 解决：即便只有两名玩家、收益矩阵全是有理数，计算 Nash 均衡仍是 $\mathsf{PPAD}$-complete（期刊版 Settling the Complexity of Two-Player Nash Equilibrium, J. ACM 2009）。两人情形格外重要，原因有二。其一，双矩阵博弈有一个特殊的良性结构：它一定存在有理数解（均衡集合是由有理数据定义的若干多面体之并，故其中必含有理数点；这与三人及以上博弈可能只有无理数解形成鲜明对比），因此原则上可以精确写出，不存在”解写不下来”的障碍。其二，求双矩阵均衡有一个经典的组合算法——Lemke-Howson 算法，它沿着多面体的边游走、必然终止于一个均衡，长期以来人们普遍寄望它（或某个变体）存在多项式时间上界。Chen-Deng 的结果一举打消了这个希望：除非 $\mathsf{PPAD}=\mathsf{P}$，否则不存在多项式算法。事实上 Savani 与 von Stengel（Hard-to-Solve Bimatrix Games, FOCS 2004 / Econometrica 2006）已构造出实例，使 Lemke-Howson 路径长度呈指数增长，与此结论遥相呼应。

需要特别强调”$\mathsf{PPAD}$-complete 意味着什么”，这是最容易踩坑的地方。

它不等于 $\mathsf{NP}$-complete。$\mathsf{PPAD}$ 是 $\mathsf{TFNP}$ 的子类，前面已说明 $\mathsf{TFNP}$ 问题不太可能 $\mathsf{NP}$-complete；把 Nash 说成”$\mathsf{NP}$-complete”是常见但严重的错误。
它并未证明 Nash 不能在多项式时间内求解。”$\mathsf{P}\neq\mathsf{PPAD}$”和”$\mathsf{P}\neq\mathsf{NP}$”一样，是一个未被证明的猜想；$\mathsf{PPAD}$-completeness 只是一个条件性（conditional）的负面证据。
它的真正含义是一种计算等价性：Nash 计算与 Brouwer 不动点、Sperner 引理、市场均衡等一大批”由不动点论证保证存在”的问题，在多项式时间归约下两两等价——要么它们全都有多项式算法，要么全都没有。换言之，找到 Nash 的高效算法将自动解决一整族看似无关的问题。

学界普遍相信 $\mathsf{P}\neq\mathsf{PPAD}$，因此普遍相信不存在高效精确算法。换句话说，Nash 给了一个深刻的负面信息：经济学里最基础的”理性预测”，其本身可能就是计算上不可行的。这动摇了”均衡是市场或博弈实际会达到的状态”这一隐含假设——如果连一台理想计算机都难以在合理时间内算出均衡，那么有限理性的真实参与者凭什么”收敛”到它？

近似 Nash（$\varepsilon$-Nash）：QPTAS 上界与 PTAS 障碍

精确求解既然难，自然退而求其次找近似均衡。这里要先把”近似”的定义和精度尺度讲清楚，否则容易误读结论。一个 $\varepsilon$-Nash 均衡是指：每个玩家通过单方面偏离所能提升的收益至多为 $\varepsilon$——形式上，对每个玩家 $i$ 和每个策略 $x_i’$，有 $u_i(x_i’,x_{-i})\le u_i(x)+\varepsilon$（通常约定收益已归一化到 $[0,1]$，这样 $\varepsilon$ 才有绝对意义）。需要注意，$\varepsilon$-Nash（”近似最优响应”）与另一个更强的概念 $\varepsilon$-well-supported Nash（要求每个被用到的纯策略本身都是 $\varepsilon$-近似最优响应）有别，本节统一指前者。

关键在于 $\varepsilon$ 取多大。在 Daskalakis、Goldberg、Papadimitriou 的 $\mathsf{PPAD}$-completeness 结果中，$\varepsilon$ 取的是关于博弈规模的逆指数（inverse-exponential，如 $\varepsilon=2^{-n}$）量级。这么小的误差在该硬度档位下本质上等价于精确求解（精度高到足以”锁定”一个真实均衡的位置），所以这一档 $\varepsilon$-Nash 同样是 $\mathsf{PPAD}$-complete。真正有趣、也真正困难的，是常数 $\varepsilon$（与博弈规模无关的固定精度，如 $\varepsilon=0.1$）的情形：此时允许的偏差不随博弈变大而缩小，问题是否就变得可处理？

上界方面，Richard Lipton、Evangelos Markakis 与 Aranyak Mehta（下文简称 LMM）给出了一个漂亮的”支撑集很小”（small support）论证。其核心是一个采样引理：在 $n\times n$ 的双矩阵博弈里，取任意一个精确 Nash 均衡 $x^*$，从它独立同分布地采样 $k=O(\log n/\varepsilon^2)$ 次纯策略并做均匀混合，由 Chernoff 界与并集界（union bound），这个 $k$ 元均匀混合策略以高概率就是一个 $\varepsilon$-Nash 均衡。因此总存在一个 $\varepsilon$-Nash 均衡，其中两名玩家都只用支撑集大小为 $O(\log n/\varepsilon^2)$ 的 $k$-均匀策略（在该小支撑上均匀混合）。证明本身不需要先知道 $x^*$——它只保证这样的小支撑解存在。于是算法就是枚举所有大小为 $k$ 的支撑集对，对每一对用线性规划检验是否能配出 $\varepsilon$-Nash。支撑集对的数目约为 $\binom{n}{k}^2\approx n^{O(\log n/\varepsilon^2)}$，这给出一个求常数精度 $\varepsilon$-Nash 的拟多项式时间近似方案（QPTAS，quasi-polynomial-time approximation scheme），运行时间约 $n^{O(\log n/\varepsilon^2)}$。注意 $n^{\log n}=2^{(\log n)^2}$ 介于多项式与指数之间，故名”拟多项式”。

那么能否把这个 QPTAS 改进成真正的 PTAS（polynomial-time approximation scheme，即对任意固定的 $\varepsilon$ 都在 $n$ 的多项式时间内求解，多项式的次数可依赖 $\varepsilon$）？答案是几乎肯定不能，这就是所谓的 PTAS 障碍。Aviad Rubinstein 在 Inapproximability of Nash Equilibrium（STOC 2016）中证明：在一个 ETH 风格的、针对 $\mathsf{PPAD}$ 的假设——即假设 $2^n$ 顶点上的 END-OF-LINE 需要 $n^{\Omega(\log n)}$（拟多项式）量级的时间，这比 $\mathsf{P}\neq\mathsf{PPAD}$ 严格更强，因为它不仅排除多项式算法、还排除拟多项式算法——之下，求某个常数 $\varepsilon$ 的 $\varepsilon$-Nash 均衡需要拟多项式时间，因此不存在 PTAS。他的硬度甚至适用于极简的博弈类（例如度数为 $3$ 的图博弈、每个玩家仅两个动作），说明难度不是来自博弈表示的庞大或复杂。这条结果的妙处在于：它把上界（LMM 的 $n^{O(\log n/\varepsilon^2)}$ QPTAS）与下界（Rubinstein 的拟多项式下界）对接在了同一个拟多项式量级上——也就是说，问题既不可能做到多项式、也不需要慢到指数，拟多项式正是它的”正确”复杂度刻度。需要说明的是，这种吻合是在拟多项式这一档意义上的：上下界关于 $\varepsilon$ 的指数依赖并不已知逐项相等，因此这是”量级吻合”而非逐项精确匹配；即便如此，能把上下界锁定在同一复杂度档位，在复杂度理论里已相当罕见。

Arrow-Debreu 市场均衡：同样是 PPAD-complete

经济学的另一块基石是 Arrow-Debreu 一般均衡（general equilibrium）。它问的是：在一个交换经济（exchange economy）里，有若干商品与若干消费者，每个消费者持有初始禀赋（endowment）并有自己的效用函数；是否存在一组商品价格，使得当每个人按这组价格卖掉禀赋、再买入自己最偏好的消费束时，所有商品的总供给恰好等于总需求（市场出清，market clearing）。Kenneth Arrow 与 Gérard Debreu 在 1954 年（Existence of an Equilibrium for a Competitive Economy, Econometrica）同样用不动点定理证明了这种均衡价格的存在性，因此它与 Nash 共享同一种”存在性来自不动点”的基因，自然也成了 $\mathsf{PPAD}$ 的候选硬问题。

一系列工作证实了这一直觉。Xi Chen、Dimitris Paparas 与 Mihalis Yannakakis 在 STOC 2013 的 The Complexity of Non-Monotone Markets（期刊版 J. ACM 2017）中引入了”非单调效用”（non-monotone utilities）这一关键概念——直观上指当某商品价格上升时，对它的需求未必单调下降的效用结构——并据此彻底解决了 CES 效用（常替代弹性，constant elasticity of substitution）市场均衡的复杂度：当 CES 参数 $\rho$ 取任意小于 $-1$ 的常数时（对应替代弹性较低、商品之间近似互补的情形），计算近似 Arrow-Debreu 市场均衡是 $\mathsf{PPAD}$-complete。配合此前对可加可分效用（additively separable）、Leontief 效用（完全互补，需求成固定比例）等情形的硬度结果，结论很清楚：市场出清价格在计算上和 Nash 均衡一样难。这进一步强化了那条统一的张力——经济学最核心的两个均衡概念，其存在性都由不动点保证，而它们的计算都落在 $\mathsf{PPAD}$ 的”不太可能高效”那一侧。

对照组之一：相关均衡可由线性规划多项式时间求出

并非所有均衡概念都这么难，这恰恰是问题最深刻的地方：难度不是”博弈”固有的，而是”你坚持要哪种均衡”造成的。相关均衡（correlated equilibrium，Robert Aumann 1974）是一个比 Nash 更宽松的解概念。设想一个值得信任的”协调者”，它先根据某个联合分布 $\pi\in\Delta(\prod_i S_i)$ 抽取一个策略组合，然后私下告诉每个玩家”建议你出的那个动作”（只告诉他自己的那一份，不透露别人的）。$\pi$ 是一个相关均衡，当且仅当：任何玩家在收到自己的建议动作后，假定其他人都会听从建议，自己也没有动机偏离到任何别的动作上。这个条件对每个玩家、每对”建议动作—备选动作”都是一条线性不等式（因为它关于 $\pi$ 的各分量是线性的）。

相关均衡与 Nash 的关系很清楚：每个 Nash 均衡都是一个相关均衡（取各玩家独立分布的乘积 $\pi=\prod_i x_i$ 即可），但相关均衡的集合更大，而且因为它由一组线性不等式（加上 $\pi\ge 0$、$\sum\pi=1$）定义，所以它是一个多面体（polytope）。这一点带来了质的差别：相关均衡集合恒非空（Nash 均衡已经在里面），且求其中任意一个点只需解一个线性规划（linear program）的可行性问题，因而在多项式时间内可解。对照前面”找一个不动点”的 $\mathsf{PPAD}$ 难度，这里的”找多面体里一个点”轻而易举——这正是凸性带来的红利。

不过还有一个隐藏的难点：对于简洁表示的多玩家博弈（图博弈 graphical game、匿名博弈 anonymous game、多矩阵博弈 polymatrix game、拥塞博弈、调度博弈等），策略组合的总数是玩家数的指数级，于是描述 $\pi$ 的变量数也是指数级，那个线性规划写都写不下，朴素求解失效。Christos Papadimitriou 与 Tim Roughgarden 在 Computing Correlated Equilibria in Multi-Player Games（J. ACM 2008）中给出了著名的 “Ellipsoid Against Hope”（对着希望跑椭球法）算法，巧妙地绕过了这个指数障碍。其思路是对偶：原始 LP 不可行（无均衡）会导出一个对偶的”违反证书”，而 Hart 与 Schmeidler 关于相关均衡存在性的证明（Existence of Correlated Equilibria, Mathematics of Operations Research 1989，用 LP 对偶／不动点论证给出相关均衡的存在性）恰好保证这种证书不存在；把椭球法（ellipsoid method）跑在对偶上，每当椭球法”以为”找到一个分离超平面时，就用存在性证明把它转化为对原始可行解的改进，最终在多项式时间（依赖于一个多项式规模的分离/期望预言机）内对一大类简洁博弈求出相关均衡。

这是整节最关键的对照：同一个博弈，仅仅换一个（更宽松、也更符合”可学习性”的）均衡概念，复杂度就从 $\mathsf{PPAD}$-complete 跌回 $\mathsf{P}$。它提示我们，难度并非博弈本身固有，而与”我们坚持要哪种均衡”密切相关。相关均衡之所以容易，还有一个更深的理由：它正是无悔学习（no-regret learning）动态自然收敛到的对象——若每个玩家各自独立地运行一个外部无悔（no-external-regret）算法反复对弈，他们的经验联合分布（empirical joint distribution）会收敛到相关均衡集合。也就是说，相关均衡不仅算得快，而且有一条可信的、分布式的”达到”路径，这与 Nash 的”算不动也学不到”形成强烈反差。

对照组之二：拥塞博弈的纯策略 Nash 是 PLS-complete

另一类对照来自纯策略（pure-strategy）均衡，即不允许混合、每个玩家只能出一个确定动作的均衡。一般博弈未必存在纯策略 Nash 均衡（最简单的反例是猜硬币 matching pennies），但拥塞博弈（congestion game，Robert Rosenthal 1973）一定存在。拥塞博弈的设定是：有一组”资源”（如道路），每个玩家选择一个资源子集（如一条由若干路段组成的路径），每个资源的代价随使用它的玩家数（拥塞程度）变化，玩家的总代价是其所选资源代价之和。Rosenthal 证明了这类博弈带有一个势函数（potential function）$\Phi$：只要某个玩家做一次能降低自身代价的改善性偏移（improving move），全局势 $\Phi$ 就会严格下降（且在标准的无权拥塞博弈里，Rosenthal 的 $\Phi$ 是一个精确势函数（exact potential），即其下降量恰等于该玩家代价的下降量；对带权博弈这一精确性不再成立，一般只有加权或序数势函数）。由于 $\Phi$ 取值离散且有下界，沿着任意改善方向走必然在有限步内停下，停下处就是一个纯策略 Nash 均衡。

于是”找纯均衡”在数学上等价于”在势函数的离散地形上做局部下降、找一个局部极小（任何单步邻域偏移都无法再降低 $\Phi$）”。这种”由局部搜索论证保证解存在”的搜索问题，由另一个 $\mathsf{TFNP}$ 子类刻画：$\mathsf{PLS}$（Polynomial Local Search，多项式局部搜索，由 Johnson、Papadimitriou、Yannakakis 1988 提出，论文 How easy is local search?）。一个 $\mathsf{PLS}$ 问题给定一个解的”邻域结构”和一个目标函数，都用多项式时间电路描述，要求找一个局部最优解；解的存在性由”目标值有界 + 每步严格改进”这条标准局部搜索论证保证。$\mathsf{PLS}$ 与 $\mathsf{PPAD}$ 是 $\mathsf{TFNP}$ 里两套不同的存在性论证，互不已知包含。

Alex Fabrikant、Christos Papadimitriou 与 Kunal Talwar 在 The Complexity of Pure Nash Equilibria（STOC 2004）中证明：一般（无权）拥塞博弈中计算纯策略 Nash 均衡是 $\mathsf{PLS}$-complete；而在对称网络拥塞博弈（symmetric network congestion game，所有玩家共享同一对源汇、策略是网络中的路径）这一特例下，可以借助最小费用流在多项式时间内求解。$\mathsf{PLS}$-completeness 有一个具体而生动的后果：因为 $\mathsf{PLS}$-complete 问题的局部搜索存在”指数长的下降链”实例，所以在某些拥塞博弈里，从几乎任何初始状态出发的改善性偏移序列，到达均衡前都可能要走指数级多步——即使每一步都在严格改进。这意味着即便”最佳响应动态”（best-response dynamics）这种最自然的学习/调整过程，也无法保证快速收敛到纯均衡。

请特别注意：Nash（$\mathsf{PPAD}$）与拥塞博弈纯均衡（$\mathsf{PLS}$）落在不同的复杂度类里。前者的难度源于不动点论证，后者源于局部搜索论证，二者刻画的是两种不同种类的”存在性证明”。这也再次印证 Papadimitriou 的分类哲学：复杂度类是按”为什么解一定存在”来切分的，而不是按问题表面长相。

承诺均衡与梯度下降：Stackelberg 与 CLS

最后看两个相关方向，它们把上面的图景延伸到优化与机器学习的语境，也补全了”$\mathsf{P}$ / $\mathsf{NP}$-hard / $\mathsf{PPAD}$ / $\mathsf{PLS}$ / 二者之交”这张地图上剩下的格子。

Stackelberg / 承诺均衡（commitment equilibrium）研究”先行者优势”。与同时出招的 Nash 不同，这里有时序：领导者（leader）先公开承诺一个（可能是混合的）策略，跟随者（follower）观察到这个承诺后再做最优响应，领导者的目标是算出那个能最大化自己收益的承诺策略。Vincent Conitzer 与 Tuomas Sandholm 在 Computing the Optimal Strategy to Commit To（EC 2006）中给出了完整图景，而且这张图景里出现了一次清晰的复杂度”相变”：

在标准型双人博弈（complete-information two-player normal-form game）中，最优混合承诺可用线性规划在多项式时间求出。直觉是：一旦固定跟随者将选择哪个最优响应动作，领导者要解的就是一个线性目标在线性约束（保证该动作确为跟随者最优响应）下的优化；对跟随者的每个动作各解一个 LP、取最好者即可。
但一旦进入 Bayesian 双人博弈（跟随者有多种私有”类型”，领导者只知其先验分布）或三人标准型博弈，计算最优承诺策略就变成 $\mathsf{NP}$-hard。

这里复杂度的”相变”来自类型不确定性与玩家数的增加，而不是来自不动点结构。所以——这是一个值得玩味的对比——尽管同属博弈论，Stackelberg 的难度用经典的 $\mathsf{NP}$-hardness 即可刻画，无需动用 $\mathsf{PPAD}$。原因在于”最优承诺”本质上是一个优化/判定问题（”是否存在承诺使领导者收益 $\ge t$”是非平凡的判定问题，可以有”否”的答案），而非全函数搜索，因此回到了经典框架。

CLS 与梯度下降则把这套理论与连续优化、神经网络训练直接挂钩。Constantinos Daskalakis 与 Christos Papadimitriou（Continuous Local Search, SODA 2011）定义了复杂度类 $\mathsf{CLS}$（Continuous Local Search，连续局部搜索），它同时带有”不动点”（$\mathsf{PPAD}$）与”局部搜索”（$\mathsf{PLS}$）两种味道，直观上对应”在一个连续域上，既要找不动点、又要做局部改善”的问题。由定义立刻有 $\mathsf{CLS}\subseteq\mathsf{PPAD}\cap\mathsf{PLS}$。长期以来人们怀疑这个包含是严格的——也就是说，”既是不动点又是局部搜索”似乎比”分别属于两类”要更强、更小。

Fearnley、Goldberg、Hollender 与 Savani 在 The Complexity of Gradient Descent: CLS = PPAD ∩ PLS（STOC 2021，J. ACM 2023）中给出了惊人的答案：$\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}$，即上面的包含其实是相等。更妙的是他们找到了一个极其自然的完全问题：在有界凸多面体域上通过梯度下降寻找一个停驻点这一问题恰好对该交集完全；具体而言，在单位正方形 $[0,1]^2$ 上、给定一个连续可微函数，计算它的一个 KKT 点（Karush-Kuhn-Tucker point，即带约束优化的一阶必要条件所刻画的点，无约束时退化为梯度为零的驻点）是 $\mathsf{PPAD}\cap\mathsf{PLS}$-complete。这是第一个落在该交集上的”自然”完全问题，而非人为构造的人工问题。

它的现实含义很值得品味：在连续博弈、以及大量机器学习目标里，”梯度下降到底要跑多久才能停在一个 KKT 点 / 局部均衡”这件看似纯工程的事，背后其实有一个精确而且很可能困难的复杂度刻度。换句话说，深度学习里梯度下降”慢得离谱”的某些最坏情形实例，可能不是调参不当，而是触碰了 $\mathsf{PPAD}\cap\mathsf{PLS}$ 这一层的内在难度——这把抽象的 $\mathsf{TFNP}$ 分类与现代 AI 实践罕见地连到了一起。需要强调的是，这一完全性结论刻画的是最坏情形实例，并不意味着典型的神经网络训练就一定困难。

小结：存在不等于可计算

把这一节串起来，主线只有一句话：均衡存在是一回事，均衡可计算是另一回事。Nash 与 Arrow-Debreu 用不动点定理保证了均衡存在，但计算它们是 $\mathsf{PPAD}$-complete；常数精度的 $\varepsilon$-Nash 也撞上拟多项式的 PTAS 障碍（LMM 的 QPTAS 上界与 Rubinstein 的下界锁定在同一拟多项式量级）。与此对照，换成相关均衡，线性规划就让它回到 $\mathsf{P}$，而且无悔学习还能分布式地收敛到它；换成拥塞博弈的纯均衡，难度类则切换成 $\mathsf{PLS}$，连最佳响应动态都可能指数级慢；承诺均衡随设定在 $\mathsf{P}$ 与 $\mathsf{NP}$-hard 之间游移，且用经典 $\mathsf{NP}$-hardness 刻画；梯度下降式的 KKT 点则精确落在 $\mathsf{PPAD}\cap\mathsf{PLS}$ 上。

这组结论共同说明，复杂度类（$\mathsf{PPAD}$、$\mathsf{PLS}$、$\mathsf{CLS}$）不是抽象的分类游戏，而是精确刻画了”哪种存在性证明对应哪种计算难度”：不动点论证给出 $\mathsf{PPAD}$，局部搜索论证给出 $\mathsf{PLS}$，二者叠加给出 $\mathsf{PPAD}\cap\mathsf{PLS}$，而凸性（线性规划）则让难度直接坍回 $\mathsf{P}$。这正是算法博弈论的核心张力，也是它对经济学的根本性追问：如果一个均衡概念在计算上不可行，那么把它当作市场或多智能体系统会实际达到的”理性预测”，可能从一开始就站不住脚。

信息设计与 Bayesian persuasion 的复杂度

到目前为止，我们考虑的博弈都假设各方对环境的信息是给定的、外生的。但在很多现实场景里，掌握信息的一方还能主动选择透露多少信息来影响别人的决策——广告商决定如何展示产品、检方决定如何呈现证据、平台决定如何推荐内容。把”信息本身当作策略变量来设计”的研究，统称为信息设计（information design）；其中最干净、影响最大的单发送者模型，就是 Kamenica 与 Gentzkow 的贝叶斯劝说（Bayesian persuasion）。本节关心的是：给定一个劝说实例，计算发送者的最优信息披露策略有多难？我们会看到一条与前几节相同味道的复杂度光谱——小规模显式输入下由线性规划多项式可解，状态空间隐式爆炸时退化为 $\mathsf{#P}$-hard 乃至不可近似，多接收者时则出现 public 与 private 信号的尖锐分野。

模型设定（Kamenica & Gentzkow 2011）

贝叶斯劝说研究的是一类信息不对称下的承诺型（commitment）博弈。设有一个发送者（sender，又称信息设计者 information designer）和一个接收者（receiver）。自然界处于某个随机的状态（state of nature）$\theta\in\Theta$，二者共享一个先验分布（common prior）$\mu_0\in\Delta(\Theta)$（这里 $\Delta(\Theta)$ 记 $\Theta$ 上所有概率分布构成的单纯形），但只有发送者能在状态实现后观察到真实的 $\theta$。接收者随后要从行动集 $A$ 中选一个行动 $a$，双方的收益（payoff）都由”行动 + 状态”共同决定：发送者收益为 $v(a,\theta)$，接收者收益为 $u(a,\theta)$。

整个博弈的时序（timing）至关重要，必须讲清楚：

发送者先公开承诺一个信号机制（signaling scheme，又称 signal / experiment）$\pi:\Theta\to\Delta(S)$，即一个从状态到信号集 $S$ 上分布的映射；$\pi(s\mid\theta)$ 表示真实状态为 $\theta$ 时发出信号 $s$ 的概率。这个机制是公开、可信、不可反悔的。
自然界按先验抽取真实状态 $\theta$，发送者观察到它。
发送者不能谎报 $\theta$，只能按已承诺的 $\pi$ 抽取一个信号 $s$ 发给接收者。
接收者看到 $s$ 后，按贝叶斯法则更新信念，得到后验（posterior）$\mu_s\in\Delta(\Theta)$，再选一个对自己最优的行动 $a^*(\mu_s)\in\arg\max_a\mathbb{E}_{\theta\sim\mu_s}[u(a,\theta)]$。

关键的张力在于：发送者无法编造状态，唯一的自由度是选择透露多少信息（即设计 $\pi$ 的粗细），但凭借第 1 步的承诺能力（commitment power），他能系统性地塑造接收者的后验、进而塑造其行为，以最大化自己的期望收益。

一个标准例子（检方—法官）。 状态 $\theta\in{\text{无罪},\text{有罪}}$，先验 $\Pr[\text{有罪}]=0.3$。法官（接收者）的行动是”定罪 / 释放”，他只在认为有罪概率 $\ge 0.5$ 时才定罪。检方（发送者）只想最大化定罪率。若检方诚实地全披露，则只有 $30\%$ 的案子能定罪。但检方可以承诺一个”调查机制”：对真有罪者总报告”有罪信号”；对真无罪者也以一定概率报告”有罪信号”，恰好把这个信号下的后验有罪概率压到 $0.5$。算下来这个信号能覆盖 $60\%$ 的案子且法官恰好愿意定罪。于是通过部分披露而非全披露，检方把定罪率从 $30\%$ 提到了 $60\%$。这个例子点出了劝说的本质：信息不是越多越好，发送者要的是把后验精确地推到接收者行为发生翻转的临界点上。

这一框架由 Kamenica 与 Gentzkow 在《Bayesian Persuasion》（American Economic Review, 2011）中奠基。

需要强调，承诺能力是劝说区别于廉价磋商（cheap talk）（Crawford–Sobel 式无承诺通信）的分水岭：没有承诺时，发送者事后总有动机背离已声明的机制，可信传递的信息量大受限制；有承诺时，机制本身成了一个可优化的对象。

凹化刻画与”信号即行动建议”的揭示原理式约简

Kamenica 与 Gentzkow 给出的核心刻画借助凹化（concavification）。注意：任何信号机制 $\pi$ 在接收者侧的效果，完全由它诱导出的后验分布决定——即一个 $\Delta(\Theta)$ 上的分布 $\tau$，描述”接收者收到信号后，其后验 $\mu_s$ 取各个值的概率”。贝叶斯一致性（Bayes-plausibility）要求这些后验的期望回到先验： $\mathbb{E}_{\mu\sim\tau}[\mu]=\mu_0.$ 反过来，任何满足该期望约束的 $\tau$ 都可由某个信号机制实现（这是 splitting lemma）。于是发送者的问题等价于：在所有”平均回到 $\mu_0$”的后验分布中，挑一个使期望收益最大。

设 $\hat v(\mu):=\mathbb{E}_{\theta\sim\mu}\big[v\big(a^*(\mu),\theta\big)\big]$ 为”当接收者后验为 $\mu$、并据此最优响应时，发送者得到的收益”（把它看成后验 $\mu$ 的函数）。则发送者的最优期望收益恰为 $\hat v$ 的凹包络（concave closure，concavification）在先验处的取值： $\mathrm{OPT}=\big(\operatorname{cav}\hat v\big)(\mu_0),$ 其中 $\operatorname{cav}\hat v$ 是不小于 $\hat v$ 的最小凹函数。直觉是：凹包络在 $\mu_0$ 处的值，正对应”把先验拆成若干后验、再加权平均”所能达到的最高收益；劝说有利可图当且仅当 $\hat v$ 在 $\mu_0$ 附近非凹（not concave），即 $\big(\operatorname{cav}\hat v\big)(\mu_0)>\hat v(\mu_0)$，发送者通过拆分后验”凸组合到更高处”。正是因为 $\hat v$ 在 $\mu_0$ 处不凹，先验的某种凸分解（splitting）才能严格抬升收益。

这一刻画还附带一个揭示原理（revelation-principle）式约简，是后续一切算法的基础。直觉是：”信号叫什么名字”无关紧要，重要的是它诱导接收者做什么。因此不失一般性，可以把信号集取为行动集本身（$S=A$），并把每个信号解读为一条行动建议（action recommendation）：”建议你选行动 $a$”。这样的机制要可行，必须满足贝叶斯激励相容（Bayesian incentive compatibility, BIC）约束，即接收者在收到建议 $a$ 时，确实愿意听从、把 $a$ 选出来：对每个被建议的 $a$ 和每个替代行动 $a’$， $\sum_{\theta}\Pr[\theta,\,\text{建议}=a]\,\big(u(a,\theta)-u(a',\theta)\big)\ \ge\ 0.$ 这条约简把原本无穷维（信号集可以任意大）的机制空间，压缩到至多”行动数那么多个信号”，从而把劝说变成了一个有限维优化问题，为算法化打开了大门。它在结构上与机制设计里”直接显示机制（direct revelation mechanism）”的揭示原理完全平行：那里把任意机制约简成”让人如实报告类型且愿意如实报告”的直接机制，这里把任意信号约简成”建议行动且愿意听从”的直接信号。

单接收者、状态行动数少：线性规划多项式时间可解

当只有一个接收者，且状态数 $

\Theta

$ 与行动数 $

$ 都较小、收益矩阵 $u,v$ 被显式给出（explicitly given）时，最优信号机制是可处理（tractable）的。利用上述”信号即行动建议”的约简，可以直接把它写成一个线性规划（linear program, LP）。

具体地，取决策变量为联合分布 $x(\theta,a)=\Pr[\text{状态}=\theta,\ \text{建议}=a]\ge 0$，即一个”状态 $\times$ 建议行动”上的概率表格。LP 为： $\begin{aligned} \max_{x\ge 0}\quad & \sum_{\theta,a} x(\theta,a)\, v(a,\theta) && \text{(发送者期望收益)}\\ \text{s.t.}\quad & \sum_{a} x(\theta,a)=\mu_0(\theta) && \forall\theta\ \text{(边际一致性：信号边际等于先验)}\\ & \sum_{\theta} x(\theta,a)\big(u(a,\theta)-u(a',\theta)\big)\ge 0 && \forall a,a'\ \text{(BIC：愿意听从建议)} \end{aligned}$ 目标线性、约束线性，且变量个数为 $|\Theta|\cdot|A|$、约束个数为 $|\Theta|+O(|A|^2)$（BIC 约束精确为每个被建议 $a$ 与每个替代 $a’\neq a$ 一条，共 $|A|(|A|-1)$ 条），都关于输入规模多项式，因此可在多项式时间内求得精确最优解。

这一观察是计算信息设计的基石，它传达一个容易被误读的信息：在小规模显式输入下，劝说本身并不困难——困难全部来自别处。难度的来源不是机制结构（结构已被揭示原理压扁成 LP），而是输入规模（状态空间是否被隐式压缩、是否指数大）与多智能体结构（一个接收者还是多个、信号公开还是私有）。下面两小段正是沿这两个维度推高复杂度。

状态数巨大或隐式给定：从 #P-hard 到不可近似

真正的复杂度跃迁发生在状态空间庞大、只能隐式（implicitly）给定的时候。一个典型情形是：发送者面对 $n$ 个相互独立的”物品 / 选项”，每个物品的好坏是一个随机变量，全局状态 $\theta$ 是这 $n$ 个变量的联合实现，于是状态空间大小为指数级 $2^n$（或更大）。此时把收益矩阵显式列出、再解前述 LP 已不可行——LP 的规模本身就爆炸了。我们必须用紧凑表示（如各物品的独立边际分布，或一个抽样预言机）来描述实例，复杂度问题随之变成”在指数大的隐式状态空间上做优化”。

Dughmi 与 Xu 在《Algorithmic Bayesian Persuasion》（STOC 2016）中，针对”多个行动、各行动收益相互独立”这一自然结构，按输入模型由易到难地刻画了复杂度。这里要先讲清 $\mathsf{#P}$ 这个类才能理解结论：$\mathsf{#P}$ 是计数复杂度类，它的问题不是”是否存在解”（那是 $\mathsf{NP}$），而是”有多少个解 / 一个指数大求和等于多少”，例如计算一个布尔公式的满足赋值个数。$\mathsf{#P}$-hard 的问题被广泛相信无多项式算法，且在多项式时间 Turing 归约（带谕示）意义下至少与整个多项式层级 $\mathsf{PH}$ 一样难（Toda 定理：$\mathsf{PH}\subseteq\mathsf{P}^{\mathsf{#P}}$，即多项式层级可由对 $\mathsf{#P}$ 谕示的多项式时间机判定）。劝说里的 $\mathsf{#P}$-hardness 正来自”对指数大的联合状态空间做精确求和”这一动作。他们的三档结论是：

独立同分布（i.i.d.）且显式给定：存在多项式时间精确算法，并对一类更一般的目标给出 $1-1/e$ 的近似算法。其技术核心借鉴拍卖理论（auction theory）中 Border 对简约型（reduced form）的刻画——Border 给出了”哪些边际分配概率向量可由某个真实联合分配实现”的多面体刻画。把它移植到劝说，就把”哪些信号边际是可实现的”刻画成一个可处理的多面体可行域，从而对信号设计做多项式时间优化。
独立但非同分布、显式给定各行动边际：计算发送者的最优期望收益是 $\mathsf{#P}$-hard 的。注意难度的定性：不是判定可行性难（那通常容易），而是对一个 $\mathsf{#P}$-完全式的求和做精确计算难——本质上要在指数大的联合状态空间上累加概率与收益。一旦各行动的随机性不再同分布，Border 式的对称结构被破坏，求和无法再被压缩成多项式表达。
一般相关分布、仅由抽样预言机（sampling oracle）隐式给定：当我们对状态分布只有”抽样访问”而无解析形式时，他们给出一个具有双标准（bi-criteria）保证的全多项式时间近似方案（FPTAS）——所谓双标准，是指算法在”逼近最优收益”的同时轻微放松 BIC 约束（接收者只需近似最优响应，即 $\epsilon$-BIC），而非严格满足。他们进一步论证：在黑箱采样模型下、于信息论意义上（不依赖任何复杂度假设），这种双标准放松是必需的、不可避免的——少量样本根本无法把严格 BIC 的可行域刻画到足够精度。

这一组结果的意义在于：一旦状态空间被压缩进紧凑的隐式表示（如各行动的独立边际、或一个抽样预言机），$\mathsf{#P}$-hardness 就成为劝说计算的内在障碍，而不再只是”LP 规模随状态数线性膨胀”那种平凡困难。换言之，硬度从”输入太大”升级成了”即便输入紧凑、计数本身也难”。

多接收者与网络：public 与 private 信号的尖锐分野

第二个推高复杂度的维度是接收者数目。当接收者从一个变成多个时，”信号传递（signaling）”分裂出两种范式根本不同的机制，二者的复杂度往往天差地别：

公开信号（public signaling）：发送者只能广播一条公开信号，所有接收者收到同一信号、看到相同后验。这相当于受限于”对所有人统一披露”。
私有信号（private signaling）：发送者可对每个接收者发送私人定制、互不相同的信号，相当于设计一组跨接收者关联（correlated）的信号通道。私有信号严格更一般（公开是它的特例：让所有私有信号取值相同即可）。

直觉上私有信号自由度更大、效力更强，但”更强”未必”更难算”——恰恰相反，下面会看到私有信号往往更易计算。

私有劝说的多智能体模型由 Arieli 与 Babichenko 在《Private Bayesian Persuasion》（Journal of Economic Theory, 2019）中提出（工作论文 2016），他们考察”多智能体、二元行动、智能体间无外部性（no externalities）“的设定（每个接收者的收益只取决于自己的行动与状态，不直接受他人行动影响）。Dughmi 与 Xu 在后续工作《Algorithmic Persuasion with No Externalities》（EC 2017）中，在该模型上允许状态数巨大，得到一个鲜明对照：

对私有信号，结论大体是正面且相当一般的。他们用线性规划对偶（LP duality）以及”分离等价于优化（separation equals optimization）“的椭球法（ellipsoid method）范式——后者是组合优化的经典原理：一个（指数大的）LP 可在多项式时间求解，当且仅当其可行域存在多项式时间的分离预言机（separation oracle）。据此他们证明，（精确）最优私有信号问题与”最大化目标函数加一个可加函数”的问题之间存在多项式时间等价；因此只要后者可处理，私有最优信号就可处理。私有信号之所以好算，关键在于”无外部性 + 私有”让各接收者的信号设计可分解，跨接收者的关联恰好被对偶变量干净地耦合起来。
对公开信号，结论是负面的：即使发送者目标是可加（additive）的、接收者只有二元行动，在 $\mathsf{P}\neq\mathsf{NP}$ 下也不存在多项式时间近似方案（PTAS）；更强地，最优公开信号在任意常数因子内都是 $\mathsf{NP}$-hard 不可近似的。他们还用实例说明，最优私有信号可以比最优公开信号好一个多项式因子，即两者不仅在计算难度上、也在效力上有本质差距。

同样的”私有易、公开难”对照在投票场景中被精确再现。Castiglioni、Celli 与 Gatti 的《Persuading Voters: It’s Easy to Whisper, It’s Hard to Speak Loud》（AAAI 2020）（标题本身就是这条分野的写照：对每个选民”耳语”私有信号容易，向全体”大声宣告”公开信号难）证明：在 $k$-投票规则（$k$-voting）与多数（plurality）规则下，最优私有信号机制可多项式时间计算；而最优公开信号在 $k$-投票规则下不能被近似到任何因子（任意倍率均 $\mathsf{NP}$-hard 不可近似），该负面结果直接推广到多数规则和匿名（anonymous）效用函数。他们进一步加强这一障碍：即便把要求放松到”只求近似最优、且允许 $\epsilon$-持久说服（$\epsilon$-persuasive，接收者只需近似而非严格最优地服从）”，公开信号仍需要拟多项式（quasi-polynomial）时间。

为什么是公开信号难、私有信号易？直觉是：公开信号被迫给所有接收者同一个后验，丧失了私有信号中那种”对每个接收者分别精调、并跨接收者关联”的自由度。这种”一个信号要同时讨好一群异质接收者”的耦合，恰恰把问题推进了组合优化的硬核（要在指数多的”哪些选民被翻转”的组合里搜索）；而私有信号因为可对每人单独设计，反而保留了 LP/对偶可分解的良好结构。这与”私有更一般、效力更强”并不矛盾：更强的机制空间不等于更难的计算问题，二者在这里恰好反向。

与 Stackelberg 博弈、机制设计复杂度的联系

贝叶斯劝说在结构上是一个两阶段的 Stackelberg 博弈：发送者作为领导者（leader）先承诺信号机制，接收者作为跟随者（follower）后做最优响应。承诺能力正是劝说与廉价磋商（cheap talk）的分水岭，也与 Stackelberg 均衡计算共享同一套 LP 与对偶工具。

这条联系是双向的：

一方面，单领导者单跟随者的 Stackelberg 混合策略可由 LP 多项式时间求得（对每个跟随者的最优响应行动各解一个 LP、再取最优），这与单接收者劝说的 LP 可解性同源——都是”领导者优化、跟随者最优响应被写成线性约束”。
另一方面，一旦引入贝叶斯类型（Bayesian types）、多个跟随者、或关联信号，问题就和贝叶斯 Stackelberg 博弈、关联均衡（correlated equilibrium）的硬度归到一起，重新落入 $\mathsf{NP}$-hard 乃至不可近似的区间——这与上一小段多接收者公开信号的硬度是同一来源（异质跟随者 / 接收者的组合耦合）。

与机制设计（mechanism design）的对照也很自然且富有启发：劝说是”设计信息、约束在激励相容下”，机制设计是”设计支付与分配、约束在激励相容下”，两者都以贝叶斯激励相容为可行域、以 LP 为基本求解器，都享有揭示原理式的直接机制约简。更深一层，劝说中由”巨大状态空间求和”导致的 $\mathsf{#P}$-hardness，与机制设计中由”对类型空间求期望 / 计算最优拍卖收益”导致的计数式难度，属于同一类计算障碍——本质都是在指数大的隐式空间上做精确求和/期望。

因此，信息设计的复杂度版图可以概括为一句话：单接收者、显式小规模时由 LP 多项式可解；状态空间隐式爆炸时退化为 $\mathsf{#P}$-hard 且仅可双标准近似；多接收者时私有信号常借 LP 对偶保持可处理，而公开信号普遍 $\mathsf{NP}$-hard 且常数因子不可近似。这与本文反复出现的主题一脉相承：决定难度的从来不是”问题听起来多复杂”，而是输入的隐式表示规模、求和/计数结构，以及多智能体耦合是否破坏了可分解性。

复杂度类速查表

下面这张表把全文出现过的复杂度类汇总到一处，方便对照与回查。这张表怎么读，有几点提醒：

“一句话定义”是判定问题（语言）层面的定义。 除非特别标注，每个类都被理解为一个语言类（一组”是/否”问题），其成员资格由某种受限的图灵机或验证器刻画。$\mathsf{#P}$ 与 $\mathsf{TFNP}$ 及其子类是例外：$\mathsf{#P}$ 是计数（函数）类，$\mathsf{TFNP}$ 家族是全函数搜索类，它们的”输出”不是一个比特而是一个数或一个解，因此不能直接和语言类放在同一条包含链上比较（详见下文的”难度地图”）。
“代表 / 完全问题”分两种角色。 “代表问题”只表示该问题属于这个类（给出一个落点）；”完全问题”则更强，表示它在相应归约下是这个类里最难的之一——把它解决就等于把整个类解决。混淆这两者是最常见的坑：例如线性规划属于 $\mathsf{P}$，但它并不是 $\mathsf{NP}$-complete 的标志性难题。
完全性依赖归约的强弱。 $\mathsf{NP}$-completeness 默认指 Karp 归约（多项式时间多对一归约）；$\mathsf{P}$-completeness 必须用更弱的归约（对数空间归约 $\le_{\log}$ 或 $\mathsf{NC}$ 归约），否则在 $\mathsf{P}$ 内部用多项式归约谈”最难”会平凡化（$\mathsf{P}$ 里任意非平凡问题都能多项式互归约）。表中”$\mathsf{P}$-完全”一行据此标注。
新增的”已知关系 / 严格性”一列记录该类与相邻类的包含关系，以及这些包含是否已被证明为严格。绝大多数关键分离（如 $\mathsf{P}$ vs $\mathsf{NP}$、$\mathsf{NP}$ vs $\mathsf{PSPACE}$）至今悬而未决——表里凡写”未知是否严格”的，都是公开难题，不要误读成”已知相等”。此外，在 $\mathsf{TFNP}$ 的各句法子类（$\mathsf{PPAD},\mathsf{PPA},\mathsf{PPP},\mathsf{PLS},\mathsf{CLS}$）之间，下文反复出现”仅在 oracle 下已知分离”这一限定，这里一次性说明：oracle（预言机）下的分离结果并不蕴含无条件分离——它只表示存在某个相对化世界使两类不等，从而排除了”它们无条件相等”的可能，但要在标准（无相对化）模型下证明严格包含，仍是公开难题。下文相应各行据此理解，不再逐行重复。

复杂度类	一句话定义	代表 / 完全问题	已知关系 / 严格性
$\mathsf{P}$	确定型图灵机在多项式时间内可判定的语言类（可高效求解的问题）。	代表性问题：线性规划（可解性判定）、最大流、有向图可达性 (PATH/STCON)；$\mathsf{P}$-完全问题（对数空间归约下）以电路值问题 (CVP) 为标准范例；线性规划（判定版，对数空间归约下亦 $\mathsf{P}$-complete）。	$\mathsf{P}\subseteq\mathsf{NP}\cap\mathsf{coNP}$；$\mathsf{P}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}$。$\mathsf{P}\subsetneq\mathsf{EXP}$ 已证（时间层级定理）；$\mathsf{P}$ 与 $\mathsf{NP}$、$\mathsf{PSPACE}$ 是否相等均未知。
$\mathsf{NP}$	存在多项式长度证书、可在多项式时间内验证”是”实例的问题类（非确定型多项式时间）。	$\mathsf{NP}$-完全代表问题：布尔可满足性 SAT / 3-SAT（Cook–Levin 定理）、团 (CLIQUE)、哈密顿回路、3-着色、子集和。	$\mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PH}\subseteq\mathsf{PSPACE}$。$\mathsf{P}\overset{?}{=}\mathsf{NP}$ 公开未决；若 $\mathsf{P}=\mathsf{NP}$ 则整个 $\mathsf{PH}$ 坍缩到 $\mathsf{P}$。
$\mathsf{coNP}$	其补问题属于 $\mathsf{NP}$ 的语言类，即”否”实例可由多项式证书高效验证（等价地，”否”实例 $x\notin L$ 拥有多项式长度的反例/否证证书）。	$\mathsf{coNP}$-完全典型问题：TAUTOLOGY（命题逻辑重言式判定，SAT 的补）、UNSAT（布尔公式不可满足性判定）。	$\mathsf{P}\subseteq\mathsf{NP}\cap\mathsf{coNP}$。$\mathsf{NP}\overset{?}{=}\mathsf{coNP}$ 未知；一般猜想 $\mathsf{NP}\ne\mathsf{coNP}$（若相等则 $\mathsf{PH}$ 坍缩到第一层）。
$\mathsf{NP}\text{-complete}$	$\mathsf{NP}$ 中最难的一类问题：既属于 $\mathsf{NP}$，又使 $\mathsf{NP}$ 中每个问题都能多项式时间（Karp）归约到它（任一被多项式求解则 $\mathsf{P}=\mathsf{NP}$）。	Cook–Levin 首个 $\mathsf{NP}$-完全问题 SAT / 3-SAT；其余如 CLIQUE、顶点覆盖、哈密顿回路、3-着色、子集和、背包（判定版）。	是 $\mathsf{NP}$ 的子集。$\mathsf{NP}$-complete 问题落入 $\mathsf{P}$ $\iff$ $\mathsf{P}=\mathsf{NP}$。若 $\mathsf{P}\ne\mathsf{NP}$，由 Ladner 定理存在既非 $\mathsf{P}$ 又非 $\mathsf{NP}$-complete 的”中间”问题。
$\mathsf{PH}$	多项式层级，由交替量词刻画的各层（$\Sigma_k^p$ / $\Pi_k^p$）之并，把 $\mathsf{NP}$、$\mathsf{coNP}$ 推广到任意有限层的预言机塔。	整个 $\mathsf{PH}$ 一般认为无完全问题（否则 $\mathsf{PH}$ 坍缩）；各层有完全问题，典型为 QBF$_k$（$k$ 段交替量词的量化布尔公式 QSAT$_k$）。	$\mathsf{NP},\mathsf{coNP}\subseteq\mathsf{PH}\subseteq\mathsf{PSPACE}$。各层是否真严格（层级是否无限）未知；一般猜想 $\mathsf{PH}$ 不坍缩。$\mathsf{PH}\overset{?}{=}\mathsf{PSPACE}$ 亦未知。
$\Sigma_2^p$	$\mathsf{PH}$ 第二层的存在层 $\Sigma_2^p = \mathsf{NP}^{\mathsf{NP}}$，刻画”存在多项式长度的 $x$，使对所有多项式长度的 $y$，一个多项式时间可判定的谓词 $R(\text{input},x,y)$ 成立”形式的问题。	$\Sigma_2^p$-完全代表问题：QSAT$_2$ / $\Sigma_2$-QBF（$\exists\forall$ 两段量化布尔公式真值判定）；极小不可满足、最小等价 DNF、若干 min-max / 双层鲁棒优化问题。	$\mathsf{NP}\cup\mathsf{coNP}\subseteq\Sigma_2^p\cap\Pi_2^p$，$\Sigma_2^p\subseteq\mathsf{PH}$。$\mathsf{NP}\overset{?}{=}\Sigma_2^p$ 未知；若相等则 $\mathsf{PH}$ 坍缩到第二层。
$\mathsf{PSPACE}$	确定型图灵机在多项式空间内可判定的语言类（等价于多项式空间非确定型，由 Savitch 定理）。	$\mathsf{PSPACE}$-完全代表问题：量化布尔公式真值 TQBF / QBF；广义版地理游戏 (Geography)、Hex、Reversi 等多项式局长的两人博弈胜负判定。	$\mathsf{PH}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}$，且 $\mathsf{PSPACE}=\mathsf{NPSPACE}$（Savitch）。$\mathsf{P}\subsetneq\mathsf{EXP}$ 已知保证 $\mathsf{P}\ne\mathsf{EXP}$，故 $\mathsf{P}\subsetneq\mathsf{PSPACE}$ 与 $\mathsf{PSPACE}\subsetneq\mathsf{EXP}$ 至少有一个严格，但两者各自是否严格均未知。
$\mathsf{EXP}$	确定型图灵机在指数时间 $2^{\text{poly}(n)}$ 内可判定的语言类（$\mathsf{EXPTIME}$），严格包含 $\mathsf{P}$。	$\mathsf{EXPTIME}$-完全代表问题：$n\times n$ 广义棋类（国际象棋、跳棋、围棋无劫等）先手必胜判定；有界交替图灵机停机、若干博弈与逻辑问题。	$\mathsf{PSPACE}\subseteq\mathsf{EXP}$，且 $\mathsf{P}\subsetneq\mathsf{EXP}$ 已由时间层级定理证明（本表唯一被证明的非平凡分离之一）。$\mathsf{PSPACE}\overset{?}{=}\mathsf{EXP}$ 未知。
$\mathsf{#P}$	计数类：对 $\mathsf{NP}$ 型问题统计接受路径/解的个数的函数问题类（由 Valiant 提出）。	$\mathsf{#P}$-完全代表问题：计算 0/1 矩阵的积和式 (Permanent)、#SAT（布尔公式满足赋值计数）、完美匹配计数、计算图的 $k$-着色方案数（固定 $k\ge 3$）。	函数类，不在语言类包含链上；$\mathsf{P}^{\mathsf{#P}}\supseteq\mathsf{PH}$（Toda 定理），故 $\mathsf{#P}$ 至少和整个 $\mathsf{PH}$ 一样”强”。Permanent 的 $\mathsf{#P}$-完全展示了”计数比判定难”：其判定版（完美匹配是否存在）在 $\mathsf{P}$ 中。
$\mathsf{TFNP}$	全函数 $\mathsf{NP}$ 搜索类：保证总有解、且解可多项式验证的搜索问题类（语义定义，一般认为无完全问题）。	因系语义类一般不被认为有完全问题；常以其句法子类（$\mathsf{PPAD}$、$\mathsf{PPA}$、$\mathsf{PPP}$、$\mathsf{PLS}$、$\mathsf{CLS}$ 等）刻画；典型问题如整数分解：其搜索版属于 $\mathsf{TFNP}$（已知落入 $\mathsf{PPP}\cap\mathsf{PPA}$）。	全函数搜索类，$\mathsf{FP}\subseteq\mathsf{TFNP}\subseteq\mathsf{FNP}$。若某个 $\mathsf{NP}$-complete 问题的搜索版落入 $\mathsf{TFNP}$ 则 $\mathsf{NP}=\mathsf{coNP}$，故一般认为 $\mathsf{TFNP}$ 不含 $\mathsf{NP}$-hard 问题。各句法子类间的分离多为 oracle 下已知、无条件未知（见表头第四点导读）。
$\mathsf{PPAD}$	$\mathsf{TFNP}$ 子类，其全性基于有向图中给定一个度为 1 的源点必存在另一度为 1 端点的”线端”原理。	$\mathsf{PPAD}$-完全代表问题：END-OF-LINE（典范问题）、计算双人博弈纳什均衡、Brouwer 不动点、Arrow–Debreu 市场均衡。	$\mathsf{PPAD}\subseteq\mathsf{TFNP}$，$\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}\subseteq\mathsf{PPAD}$。是否 $\mathsf{PPAD}=\mathsf{FP}$（即均衡可高效计算）未知，一般强烈猜测不等。与 $\mathsf{PPA}$、$\mathsf{PPP}$ 的相对关系仅在 oracle 下已知分离。
$\mathsf{PPA}$	$\mathsf{TFNP}$ 子类，其全性基于”无向图中奇度顶点个数为偶”的奇偶原理（$\mathsf{PPAD}$ 的无向类比）。	$\mathsf{PPA}$-完全代表问题：LEAF（无向图给定一个叶子求另一叶子）、Consensus-Halving（共识对半）、Borsuk–Ulam、Necklace-Splitting 等。	$\mathsf{PPA}\subseteq\mathsf{TFNP}$，且 $\mathsf{PPAD}\subseteq\mathsf{PPA}$（有向蕴含无向奇偶）。$\mathsf{PPAD}\overset{?}{=}\mathsf{PPA}$ 未知；一般猜测严格包含。
$\mathsf{PPP}$	$\mathsf{TFNP}$ 子类，其全性基于鸽笼原理：$n$ 比特到 $n$ 比特电路必有映到 $0^n$ 的输入或一对碰撞输入。	$\mathsf{PPP}$-完全代表问题：PIGEON（典范鸽笼电路问题）；Equal-Sums、constrained-SIS（cSIS，constrained Short Integer Solution；Sotiraki–Zampetakis–Zirdelis, FOCS 2018 证其 $\mathsf{PPP}$-完全）等格密码相关问题。注：最短向量问题 SVP 与 $\mathsf{PPP}$ 的关系仅被讨论，尚未证明 $\mathsf{PPP}$-完全。	$\mathsf{PPP}\subseteq\mathsf{TFNP}$，且 $\mathsf{PPAD}\subseteq\mathsf{PPP}$。是否 $\mathsf{PPAD}\subsetneq\mathsf{PPP}$ 未知；$\mathsf{PPP}$ 与 $\mathsf{PPA}$ 互不包含关系亦仅 oracle 下已知。
$\mathsf{PLS}$	多项式局部搜索类：邻域内可多项式时间验证并改进、求局部最优解的全搜索问题类。	$\mathsf{PLS}$-完全代表问题：Local-Max-Cut（单点翻转邻域的局部最大割）、加权满足的 FLIP、局部最优 TSP（k-opt）、拥塞博弈纯纳什均衡。	$\mathsf{PLS}\subseteq\mathsf{TFNP}$，$\mathsf{CLS}\subseteq\mathsf{PLS}$。一般认为 $\mathsf{PLS}$ 与 $\mathsf{PPAD}$ 互不包含（oracle 下已分离）；$\mathsf{PLS}=\mathsf{FP}$ 是否成立未知。
$\mathsf{CLS}$	连续局部搜索类，$\mathsf{CLS} = \mathsf{PPAD} \cap \mathsf{PLS}$，刻画连续域上兼具不动点与局部优化结构的全搜索问题。	$\mathsf{CLS}$-完全代表问题：Continuous-Localopt / 3D-Continuous-Localopt、End-of-Potential-Line；一般情形的梯度下降（找近似稳定点）亦为 $\mathsf{CLS}$-完全。	$\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}$（Fearnley–Goldberg–Hollender–Savani 2021 证明该刻画），夹在两类之间。$\mathsf{CLS}=\mathsf{FP}$ 未知；它是 $\mathsf{TFNP}$ 内”最贴近可解”却仍未被证可解的代表类。

难度地图与小结

如果只带走两条主线，应该是这两条；它们贯穿了从图灵机到博弈均衡的全部内容。

第一条主线：”存在 $\ne$ 可计算”——复杂度是为”原则上能否高效求解”立的标尺。 复杂度理论从一开始就把问题从”能不能做”切换到”能不能高效地做”。一个对象的存在性往往由经典的拓扑或组合定理免费保证：Nash 均衡的存在来自 Brouwer / Kakutani 不动点定理，Arrow–Debreu 市场均衡的存在同样来自不动点论证，相关均衡（correlated equilibrium）的存在性则可由线性规划对偶（或 no-regret 动态）直接给出，不依赖不动点定理。但存在性证明往往是非构造的——它告诉你”解一定在那里”，却不给你在多项式时间内找到它的算法。复杂度类正是用来量化这道鸿沟的尺子：$\mathsf{P}$ 圈出”可高效求解”，$\mathsf{NP}$ 圈出”可高效验证”，而 $\mathsf{TFNP}$ 及其子类（$\mathsf{PPAD},\mathsf{PPA},\mathsf{PPP},\mathsf{PLS},\mathsf{CLS}$）专门刻画那些保证有解、却疑似难找的搜索问题。对博弈论与经济学而言，这一课最为锋利：Nash 均衡总存在（Brouwer 保证），却是 $\mathsf{PPAD}$-complete，即在标准猜想下没有多项式算法；相关均衡同样总存在，却能用线性规划在多项式时间内精确求出，因为它的解集本身就是一个由线性约束界定的凸多胞形；Bayesian persuasion 在单接收者下退化为一个线性规划（因而可高效求解），在多接收者或状态空间爆炸时却迅速滑向 $\mathsf{NP}$-hard 乃至 $\mathsf{#P}$-hard。同一个”均衡”或”机制”的名字背后，可能藏着天壤之别的计算命运——这正是”存在”与”可计算”必须分开看的原因。

第二条主线：”归约是丈量难度的尺子”——它把对一个问题的判断传递到成千上万个问题。 复杂度理论之所以能形成这张地图，关键工具是归约 (reduction)。一个归约 $A\le B$ 把对 $A$ 的求解转化为对 $B$ 的求解，从而断言”$B$ 至少和 $A$ 一样难”。归约让”难度”成为可传递、可比较、可定位的量：Cook–Levin 定理用一次构造性归约把所有 $\mathsf{NP}$ 问题压到 SAT 身上，确立了第一个 $\mathsf{NP}$-complete 问题；此后 Karp 的归约链把这种难度像火炬一样传到 21 个组合问题，再到今天的成千上万个。同一套方法论在 $\mathsf{TFNP}$ 世界里复刻：END-OF-LINE 之于 $\mathsf{PPAD}$、PIGEON 之于 $\mathsf{PPP}$、Local-Max-Cut 之于 $\mathsf{PLS}$，都是用归约把整类问题的难度锚定到一个”典范问题”上，于是”Nash 均衡和 Brouwer 不动点一样难”这样的论断才有了精确含义。归约也是这张速查表的脊梁：每一个”完全问题”都是一条归约链的端点，每一处”$X$-hard”都是一次难度的横向传递。读懂这张难度地图，本质上就是学会问两个问题——它存在吗（由数学保证），以及它能算吗（由归约定位）——并且知道在 $\mathsf{P}$、$\mathsf{NP}$、$\mathsf{PSPACE}$、$\mathsf{#P}$、$\mathsf{PPAD}$ 这些坐标里，一个漂亮的均衡概念或机制究竟落在”能算的”一侧，还是只停在”存在的”一侧。

Mathematics, Algorithm

This post is licensed under CC BY 4.0 by the author.