On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

Papadimitriou

Background：

只能输出yes或者no（做判定）的接收/拒绝图灵机是传统计算复杂性研究的重点，P和NP是此中最为经典的复杂性类；然而当我们考虑输出更加复杂的图灵机时，有一些类似的结构是值得注意的。例如，类似于P和NP，我们可以定义FP和FNP：
FP: a binary relation  P ( x , y )  is in FP s.t.  ∃  a DTM S, for any given  x , can find a  y  such that  P ( x , y )  Holds in Poly(|x|) time \text{FP: a binary relation $P(x,y)$ is in FP s.t. $\exists$ a DTM S, for any given $x$,} \\\text{can find a $y$ such that $P(x,y)$ Holds in Poly(|x|) time} FP: a binary relation P(x,y) is in FP s.t. ∃ a DTM S, for any given x,can find a y such that P(x,y) Holds in Poly(|x|) time

FNP: a binary relation  P ( x , y )  is in FP s.t.  ∃  a DTM S, for any given  x , y , can check if  P ( x , y )  Holds in Poly(|x|) time \text{FNP: a binary relation $P(x,y)$ is in FP s.t. $\exists$ a DTM S, for any given $x,y$,} \\\text{can check if $P(x,y)$ Holds in Poly(|x|) time} FNP: a binary relation P(x,y) is in FP s.t. ∃ a DTM S, for any given x,y,can check if P(x,y) Holds in Poly(|x|) time

然后，我们还可以定义TFNP。TFNP类与FNP略有区别，定义为所有多项式时间可验证的多值函数语言，也就意味着它保证了解一定存在。

显然，我们有FP ⊆ \subseteq ⊆TFNP ⊆ \subseteq ⊆FNP，但是我们既不知道FP是否=TFNP，也不知道TFNP是否等于FNP。

当我们希望解决计算复杂类的难题时，一个最常用的方法就是通过考虑complete的问题来抓住这个复杂度类的核心。然而，由于TFNP是个语义（semantic）类（对结果的数量存在某些定量要求），而这种复杂性类一般认为不存在complete的问题，因此我们也许应该考虑一些TFNP的非语义子类，以便进行complete属性的讨论。

语义类中的自然成员往往具有某些数学证明，以证明其在这个类中，在TFNP中就表现为证明某些问题确实至少有一个解。那么，我们就可以进一步地按照TFNP类的自然成员的证明方法对其进行分类。在组合优化问题中，我们常常使用二元性（duality）证明问题解的存在性。

在之前的文章中，我们已经定义了PLS这个复杂性类。PLS定义为一个组合优化问题——我们希望能够在图中找到一个局部极小值点。其存在性由定理：每个有向循环图都至少有一个聚点来保证。

那么，自然地，我们希望找到其他的存在性证明启发的TFNP的子类。在所有存在性问题中，我们最熟知的当属Brouwer不动点问题了——任意一个d维simplex上的变换f都会有一个不动点。当然，事实上在计算不动点时会有近似度 ϵ \epsilon ϵ，而我们希望这个问题BROUWER能够对d和-log ϵ \epsilon ϵ具有多项式时间复杂性。但事实上，在之前的论文中，我们说明了，如果把f看成一个谕示，那么在两个参数上，不动点的计算最坏情况下都有指数复杂度。这不是我们希望的结果，因此，在这篇文章中，我们会更换对f的定义方式，以得到更好的复杂性结果。

我们基于parity argument（握手定理）定义新复杂性类PPA（polynomial parity argument）。握手定理是非常常见也很基础的一个定理：每个有限图都有偶数个奇度顶点。这个定理的一个有趣推论是Smith定理：每个度数均奇的图都恰有偶数个哈密顿回路过同一条边。由此，我们可以定义SMITH问题：给定一个奇度图G和其中的一条哈密顿回路，求出另一条哈密顿回路。显然这个问题在TFNP中，但是事实上也可以囊括进我们定义的新的类中。

首先我们来看握手定理的一个推论：
如 果 一 个 图 中 每 个 顶 点 度 数 至 多 为 2 ， 则 其 有 偶 数 个 叶 子 节 点 。 如果一个图中每个顶点度数至多为2，则其有偶数个叶子节点。 如果一个图中每个顶点度数至多为2，则其有偶数个叶子节点。
这个问题和SMITH很像，而且看起来是SMITH的一个特例。事实上，基于这个推论，我们又想到了Sperner引理：
如 果 我 们 对 一 个 三 角 剖 分 （ 注意，不要求是规则的三角剖分 ） 做 0 , 1 , 2 染 色 ， 并 且 要 求 第 i 条 边 的 颜 色 中 不 能 出 现 ( 2 − i ) ， 那 么 其 中 必 定 有 一 个 三 色 三 角 形 。 如果我们对一个三角剖分（\textbf{注意，不要求是规则的三角剖分}）做0,1,2染色，\\并且要求第i条边的颜色中不能出现(2-i)，那么其中必定有一个三色三角形。 如果我们对一个三角剖分（注意，不要求是规则的三角剖分）做0,1,2染色，并且要求第i条边的颜色中不能出现(2−i)，那么其中必定有一个三色三角形。
证明正是用到了刚才的握手定理：首先在三角形的1,2两条边的交点处的三角形必定是0,1双色，否则已证。接下来考虑所有恰好包含0,1双色的三角形。显然每两个这样的三角形至多共一条边，并且每个这样的三角形恰好含有两条两端点分别为0,1双色的边。以0,1三角形为顶点构造图G，两个顶点连边当且仅当其代表的三角形共0,1边。那么，每个顶点的度数至多为2，而在第2条边上由于左端点0右端点1，因此中间必然有奇数条0,1边，每个包含0,1边的三角形不妨设是双色，因此这些边所在的三角形就是所有的叶子节点，有奇数个，因此必定还会在内部有一个叶子节点，那么叶子节点对应的三角形的某一个相邻三角形必定为0,1,2三色三角形，证毕！

不过，我们注意到这个方法用在SMITH上可能会有细微的差别。在解决SMITH问题的时候，我们的选择是一个序贯的过程，也就是说图G会变成一个有向图。当然，握手定理还是成立的，只不过我们的复杂度类会变成PPAD（polynomial parity argument in a directed graph）；如果我们从一个路径的中间开始，那么我们又可以定义复杂度类PMPA。我们不知道PPA是否等于PPAD。

我们的直觉介绍完毕，下面是这篇文章的主要工作：我们首先定义了引入的类PPAD和PPA，然后证明了若干问题（例如，Kakutani，Nash-Equilibrium）in PPA/PPAD的性质；并且我们说明，如果我们严格要求寻找指定顶点所在路径的另一端点，那么复杂度将会是PSPACE；最后我们证明以上这些问题是PPA/PPAD-complete的。

Section 2

我们先给出PPA的严格定义：
对 于 问 题 A , 输 入 为 x ， 配 置 C ( x ) = Σ p ( ∣ x ∣ ) ， 其 中 p 为 多 项 式 。 对 于 ∀ c ∈ C ( x ) ， 一 个 D T M 可 以 在 多 项 式 时 间 内 返 回 一 个 集 合 M ( x , c ) ， 其 中 至 多 有 两 个 配 置 如 果 某 两 个 配 置 c , c ′ 相 互 在 M 中 ， 则 称 为 邻 居 ， 记 为 [ c , c ′ ] ∈ G ( x ) ， 这 样 G ( x ) 就 是 我 们 需 要 的 图 了 。 我 们 要 求 M ( x , 00 … 0 ) = { 11 … 1 } ， 且 00 … 0 ∈ M ( x , 11 … 1 ) （ 亦 即 一 个 叶 子 ） ， 要 求 找 到 另 一 个 叶 子 对于问题A,输入为x，配置C(x)=\Sigma^{p(|x|)}，其中p为多项式。\\ 对于\forall c\in C(x)，一个DTM可以在多项式时间内返回一个集合M(x,c)，其中至多有两个配置\\ 如果某两个配置c,c^{'}相互在M中，则称为邻居，记为[c,c^{'}]\in G(x)，这样G(x)就是我们需要的图了。\\ 我们要求M(x,00\dots0)=\{11\dots1\}，且00\dots0\in M(x,11\dots 1)（亦即一个叶子），要求找到另一个叶子 对于问题A,输入为x，配置C(x)=Σp(∣x∣)，其中p为多项式。对于∀c∈C(x)，一个DTM可以在多项式时间内返回一个集合M(x,c)，其中至多有两个配置如果某两个配置c,c′相互在M中，则称为邻居，记为[c,c′]∈G(x)，这样G(x)就是我们需要的图了。我们要求M(x,00…0)={11…1}，且00…0∈M(x,11…1)（亦即一个叶子），要求找到另一个叶子
插播：为什么我们的配置C(x)，相当于图，节点数量是 2 p ( ∣ x ∣ ) 2^{p(|x|)} 2p(∣x∣)量级的，而不是正常的组合问题的p(|x|)量级?

答：因为在定义C(x)的时候我们相当于只给出了一个电路M，M可以给出某个顶点的两个邻居。因此，我们的输入长度和一个顶点的总字节数相当（n）（但代价是除了一个一度顶点之外一无所知）。然而，在普通的组合问题中，输入是整个图G，包含了一切顶点编码和连边信息，输入长度已经达到了n^2级别。

为了PPA包含类似HAMILTON这样的问题，我们可以扩充定义 P P A ′ PPA^{'} PPA′，使得 ∣ M ( x , c ) ∣ |M(x,c)| ∣M(x,c)∣可以是|x|的多项式大小，然后给定一个奇度顶点，寻找另一个。

定理1： P P A = P P A ′ PPA=PPA^{'} PPA=PPA′

证明：把一个顶点拆成若干个顶点即可，容易构造一个多项式时间的归约。

然后，我们给出PPAD的定义。事实上，只要给PPA的定义中的配置增加一个序关系即可，即M(x,c)的内的第一个元素代表前驱，第二个代表后继，我们要求的则是另一个出入度和为1的顶点。

命题1： F P ⊆ P P A D ⊆ P P A ⊆ F N P FP\subseteq PPAD \subseteq PPA \subseteq FNP FP⊆PPAD⊆PPA⊆FNP

如果我们严格要求寻找给定的顶点所在路径的另一个端点，记为复杂性类 P P A ′ ′ PPA^{''} PPA′′

定理2： P P A ′ ′ = P P A D ′ ′ = F P S P A C E PPA^{''}=PPAD^{''}=FPSPACE PPA′′=PPAD′′=FPSPACE

根据Bennett定理，任何一个FPSPACE中的问题可以被一个多项式空间限制的的递归图灵机T解决，也就是说，每一个格局都是其它至多一个的前驱或者后继。

命题2：如果我们定义问题 P P A ′ ′ ′ PPA^{'''} PPA′′′为使得 ∣ M ( x , c ) ∣ ≤ 3 |M(x,c)|\leq 3 ∣M(x,c)∣≤3的问题，那么可以证明 P P A ′ ′ ′ = F N P PPA^{'''}=FNP PPA′′′=FNP

Section 3

Problems in PPAD

SPERNER：之前提到的三角形剖分上的Sperner定理实际上可以推广到任意维度的simplex上。对于n维simplex的任意剖分，事实上都存在一个n色simplex。但是，当我们将计算问题推广到n维的时候可能会出现一些问题：n( ≥ 3 \geq 3 ≥3)维的simplex并不存在一个标准剖分，也就是不够规则，这可能会为我们之后对完全性的分析带来问题。为此，我们对simplex做同胚变换得到一个cube，然后对这个cube考虑我们的结论。

通过上面的示例，我们可以使用cube n 3 n^3 n3的n条边来模拟simplex的n条边，然后用剩下的所有面模拟剩下的一个平面。最后对每个小cube做分割。那么，我们就可以用三角剖分的Sperner定理证明在cube中的Sperner定理。最终，我们得到了nD-SPERNER问题，并且根据与上面相同的证明方法，我们知道 n D − S P E R N E R ∈ P P A nD-SPERNER\in PPA nD−SPERNER∈PPA

接下来我们借助SPERNER考虑Brouwer的问题。首先考虑连续的Brouwer：对于连续的Brouwer，我们可以采用SPERNER逼近的方法来处理，只要逐渐提高剖分的精度，即可得到一个闭区间列（由各个精度下的SPERNER计算得到的三角形给出），然后根据Weierstrass定理得到一个聚点，即为所求的不动点。这里的处理手法是考虑x->f(x)的方向，根据方向染成0,1,2三种颜色，即可保证SPERNER的边界条件，并且三个顶点分别染三种颜色的三角形处取极限小时就说明这一点处x-f(x)的方向变化很快，说明x=f(x)。

其次，我们定义BROUWER计算问题。根据上面的Sperner定理，在f的一个剖分插值（在 [ 0 , 1 ] d [0,1]^d [0,1]d内部，所有坐标为 1 n \frac{1}{n} n1​的倍数的顶点集合（共 n d n^d nd个））上，我们可以给出一个图灵机M在多项式时间内返回其中一个顶点x，使得 ∣ f ( x ) − x ∣ < 1 n |f(x)-x|<\frac{1}{n} ∣f(x)−x∣<n1​。并且，其计算复杂度 in PPAD.

之后，我们定义NASH计算问题，即计算一个双人博弈的Nash均衡。根据https://core.ac.uk/download/pdf/82658599.pdf提出的Lemeke迭代算法，我们得知Nash的计算复杂度包含在PPAD之中。

还有其他复杂性类也在PPAD中，这里不再赘述证明过程，把问题列举如下：

Competitive Equilibrium, Kakutani; Borsuk, Ulam and Tucker; Necklace Splitting, Discrete ham sandwich; P-LCP

Problems in PPA

定理1：SMITH in PPA

我们之前已经讨论过了。

还有其他复杂性类也在PPAD中，这里不再赘述证明过程，把问题列举如下：

Another Hamilton Path; Hamilton Decomposition; TSP Nonadjacency; Chevalley mod ; Totally Even Subgraph

Section 4

在本节中，我们讨论Nash的完全性问题，也是这篇文章的核心问题。

定理：3D-SPERNER is PPAD-complete

为此，我们只要证明任何一个PPAD问题都可以归约到3D-SPERNER. 首先，我们先明确我们现在的目的：
如 果 A 在 P P A D 中 ， 就 意 味 着 存 在 一 个 算 法 M ， 对 于 任 意 一 个 输 入 x 以 及 任 意 节 点 v ∈ { 0 , 1 } N , N = ∣ x ∣ k ， M ( x , v ) ∈ { 0 , 1 } 2 N ， 我 们 需 要 基 于 x 和 M 构 造 一 个 n ∗ n ∗ n 的 S p e r n e r 问 题 ， 并 保 证 进 行 的 是 多 项 式 归 约 。 如果A在PPAD中，就意味着存在一个算法M，对于任意一个输入x以及任意节点v\in \{0,1\}^N,N=|x|^k，\\ M(x,v)\in \{0,1\}^{2N}，我们需要基于x和M构造一个n*n*n的Sperner问题，并保证\\ 进行的是多项式归约。 如果A在PPAD中，就意味着存在一个算法M，对于任意一个输入x以及任意节点v∈{0,1}N,N=∣x∣k，M(x,v)∈{0,1}2N，我们需要基于x和M构造一个n∗n∗n的Sperner问题，并保证进行的是多项式归约。
我们在这里不涉及过多细节，只讲证明的思路：首先取n= 2 3 N 2^{3N} 23N，然后让大部分顶点染成颜色0，通过构造1,2,3构成的“tube（管道）”的行为来模拟PPAD在图G(x)上的行为。首先考虑G(x)的 2 N 2^{N} 2N个顶点，把它们均匀地排列在与正方体的某条边距离非常近的平行线上。然后，图G中的边（至多 2 N 2^N 2N条）均匀排列在正方形这条边的对边上，如图所示：

在这里插入图片描述

图中的短折线代表顶点和边，长折线代表连通方向。例如，e为i->j的有向边，那么将i的下端点和e的左端点连接，将e的右端点和j的上端点连接。这样，我们就得到了一个SPERNER问题，并且我们知道管道在顶点v开始/终止当且仅当v为G(x)的奇度顶点，也就当且仅当管道在该处出现0,1,2,3四色cube。并且我们已知初始顶点00…0为奇度顶点，要求找另一个奇度顶点就等价于找SPERNER问题的一个解了。

此外还有一些细节，例如取恰当的管道粗细，证明这些管道不会相互交叉，归约是多项式内完成的，管道在移动过程中可以通过恰当的旋转保持1,2,3三色的位置等等，都是有直觉支撑的细节，我们在这里忽略证明。

推论：BROUWER, KAKUTANI, EXCHANGE ECONOMY, 3-TUCKER, BORSUK-ULAM都是PPAD完全的

Section 5

Further works：
懒得翻译了，因为和论文思路也没什么关系。