当对数空间复杂性遇上强联通图和行列式

本文介绍了对数空间复杂性, 譬如如何刻画空间复杂性 (Immerman-Szelepcsényi 定理), 以及一些常见图论问题 (如判断图的连通性, 或者找图的强联通分量) 的对数多项式空间算法. 诸如此类的图论问题有广为人知的多项式时间算法, 因而也在各类算法竞赛中屡见不鲜, 对数空间复杂性的一系列结果也许是引入计算复杂性理论的很好的切入点. 有趣的是, 类似图的连通性这样的问题^[1], 也可以在量子计算 (具体来说是哈密顿量) 的上下文中定义类似的问题^[2], 并证明空间复杂性有关的结果.

除此之外, 空间复杂性也和条件数良好的整数矩阵的行列式计算有关. 尽管对于经典对数空间复杂性, 我们只有非确定性时间的对数空间算法 ($\sf NL$), 但是这一问题却有量子对数空间算法^[3] (启发自求解线性系统的著名的 HHL 算法). 最近的一些尝试^[4]得到了一些中间结果, 我们能证明 ${\sf NL}={\sf L}$ 吗?

下面开始正文.

从图的强联通性说起

给定顶点标号为长度-$n$比特串的有向图 (即至多有 $2^n$ 个顶点), 判断这个有向图是否是强连通 (strongly connectivity) 的不但有多项式空间 ($\sf PSPACE$) 算法, 而且这个问题实际上还是 $\sf PSPACE$-complete 的. 这个问题和空间复杂性理论有很深的联系, 事实上我们还可以证明更强的结果:

定理 1. 对于所有 $\Omega(\log(n)) \leq s(n) \leq {\rm poly}(n)$, 给定顶点能被长度-$n$ 高效编码的有向图, 即顶点标号的长度不超过 $s(n)$, 判断这个有向图是否强连通有 ${\sf NSPACE}[O(s(n))]$ 的算法, 并且这一问题在 ${\sf SPACE}[s(n)]$ 的规约下是 ${\sf NSPACE}[O(s(n))]$-complete 的.

当 $s(n)=\Theta(\log(n))$ 的时候, 这一问题是 $\sf NL$-complete 的. 这一结果的证明并不平凡, 尽管可以在本科层次的计算理论教材上找到 (比如 Sipser). 注意到一个有向图是强联通的, 当且仅当图上的任意两个顶点之间都存在一条连通路径. 那么我们可以设计一个 coNL 算法, 非确定性的选择一对顶点 $s,t$ , 然后看看他们之间是否存在连通路径 ($s,t$-connectivity).

Immerman 和 Szelepcsényi 在上世纪八十年代末, 分别独立证明了 ${\sf NL}={\sf coNL}$, 这一结果荣膺 1995 年的 Godel Prize – 可以说跟 Cook-Levin 定理, 还有求解线性规划的内点法 (interior-point method) 一样是冷战遗产了, 希望接下来的一二十年不会有更多的新冷战遗产.

另外, 注意到多项式的多项式仍然是多项式, 那么Savitch 定理 (1970) 可以导出 ${\sf NPSPACE}={\sf PSPACE}$. 即考虑 $f(n)$ 是多项式的情况, 带入 $\forall f(n)\geq \log(n), {\sf NSPACE}(f(n)) \subseteq {\sf SPACE}(f^2(n))$. 那么定理 1 证明了, 给定指数多个顶点的有向图, 判定它是否是强联通的是 $\sf PSPACE$-complete 的.

我会在下一节证明定理 1, 并在之后简单介绍与之相关的 open problem 和新结果.

如何在多项式空间中判断图的强连通性?

到现在为止, 如果我们把这一节中 $n$ 个顶点的有向图换成 $2^n$ 个顶点的有向图, 那么我们就得到了一个 NPSPACE 算法: 非确定性地枚举有向图中的顶点对, 验证他们直接是否不存在连通路径.

Savitch 定理告诉我们, 这样的算法可以用 PSPACE 算法来模拟. 做法就是考虑 NPSPACE 计算中的两个 configuration $a,b$ 和这样的计算的步数 $t$, 考虑这两个 configuration $a,b$ 的计算中间的 configuration $m$ , 分别验证 $(a,m)$ 和 $(m,b)$ 能不能用 $t/2$ 步的非确定性多项式空间算法完成, 然后继续递归 . 由于每一步验证都需要多项式空间 $f(n)$ , 而可能的计算路径的深度$d(n) \leq O(2^n)$, 我们可以用 $f(n) \log d(n)$ 的空间, 即多项式空间模拟. 综合以上步骤, 即判断图强联通性的 $\sf co\text{-}NPSPACE$ 算法 - 对应的 $\sf NPSPACE$ 算法 - 用以模拟的 $\sf PSPACE$ 算法, 我们得到了判断指数规模的有向图是否强联通的多项式空间算法.

哈密顿量基态的"连通性"

首先多写两个有趣但不是那么重要的结果. 也即 PSPACE-complete 版本的 s,t-connectivity, 我们还可以证明它的一些有趣的变种, 比如说布尔表达式的满足赋值的"连通性", 或者哈密顿量的基态的"连通性", 也是 PSPACE-complete 的.

我们知道带量词 (quantifier) 的布尔函数的可满足性是 PSPACE-complete 的, 那么如果给定两个满足的赋值 (assignment), 我们可以判断是否存在一条这两个赋值之间的连通路径吗? 即每次只更改一个变量的值, 但是新的赋值仍然满足这个布尔表达式. 这一问题除了很简单的情形有多项式时间算法, 其他时候都是 PSPACE-complete 的 ^[1:1].

有趣的是, 这一问题的量子版本也是对的. 我们可以定义一个 local Hamiltonian, 并询问它的指数精度的基态能量, 这一问题是 PSPACE-complete 的 ^[5]. 那么如果给定这个 local Hamiltonian 的两个基态, 我们能不能判断这两个基态是不是"连通"的呢? 如果我们只允许作用单比特量子门, 那么判断这样的指数长的"连通"两个基态的量子门序列是否存在也是 PSPACE-complete 的 ^[2:1].

对数空间复杂性浅说

PATH is NL-complete

首先考虑一个类似的问题: 给定一个 $n$ 个顶点的有向图 (即顶点的二进制编号长度为 $\Theta(\log(n))$), 和图上两个顶点 $s,t$, 那么这两个顶点之间是否存在连通路径呢? 这个问题通常被称作 st-connectivity ($\sf STCON$) 或者 $\sf PATH$, 可以证明它是 $\sf NL$-complete 的, 证明包括两个部分:

(1) $\sf PATH$ 的 $\sf NL$ 算法

由于只有 $n$ 个顶点, 不妨给每个顶点一个 $\log(n)$ 长度的二进制编号, 那么我们可以在对数空间里盯着一个顶点 $s$, 然后看看它的邻居是谁. 由于这里还能用非确定性, 所以我们可以同时看着它的所有邻居, 并且不断重复这个过程, 直到我们看到了 $t$. 由于只有 $n$ 个顶点, 所以在 $n$ 步之后还不能同时看到 $s,t$ 的话, 那么他们肯定是不连通的.

(2) $\sf PATH$ 是 $\sf NL$-hard 的

考虑一个对数空间的非确定性图灵机, 我们把纸带上写的东西记作 configuration. 于是我们可以根据这个图灵机的转移情况构造一个图, 每个 configuration 是图上的一个顶点; 而两个顶点之间有边, 仅当我们可以用非确定性对数空间的一步计算从一个 configuration 跳到另一个 configuration. 那么任何的非确定性对数空间的计算, 都可以写成一个这样的有向图. 由于图的顶点 (configuration) 的二进制编号长度是 $\log(n)$, 不难验证这里的规约只用了对数空间.

所以给定 $n$ 个顶点的有向图和两个顶点, 判断顶点之间是否有连通路径是 $\sf NL$-complete 的.

2-SAT is NL​-complete

我们在上一节简单提及了判断有向图是否强联通的 $\sf co\text{-}NL$ 算法, 非确定地选取一对顶点, 然后看看是不是连通路径不存在. 类似地, 我们还可以证明:

定理 2. $\sf 2\text{-}SAT$ 也是 $\sf NL$-complete 的.

做法并不复杂, 把 2-SAT 和子句 $c_j = (x_{i_1} \vee \neg x_{i_2} \vee x_{i_5})$ 当成二分图的一边, 然后把变量 $x_i$ 和它的 negation $\neg x_i$ 当成二分图的另一边; 然后用 PATH 的 $\sf co\text{-}NL$ 算法, 分别判断:

• $x_i$ 到 $\neg x_i$ 的路径是否存在, 不存在的话直接拒绝, 因为找不到满足布尔表达式的 assignment;
• $\neg x_i$ 到 $x_i$ 的路径是否存在, 存在的话直接拒绝, 因为前面找到的 assignment 是自相矛盾的.

由于判定有向图是否强联通是有多项式时间算法的, 不难得出$\mathsf{NL}\subseteq\mathsf{P}$. 但是众所周知 3-SAT 是 $\sf NP$-complete 的 (Cook-Levin 定理, 1971), 并且另一方面, 用空间谱系定理 (space hierarchy theorem) 可以导出 $\mathsf{NL} \subsetneq{\sf PSPACE}$. 于是 ${\sf NL} \subseteq {\sf P} \subseteq {\sf NP} \subseteq {\sf PSPACE}$ 之中, 必然有一环是真包含.

Immerman–Szelepcsényi 定理

Immerman–Szelepcsényi 定理. 对于所有 $s(n) \geq \log(n)$ , ${\sf NSPACE}(s(n)) = {\sf co\text{-}NSPACE}(s(n))$ 都成立.

接下来简单说一下 Immerman–Szelepcsényi 定理的证明. 也就是说, 给定 $n$ 个顶点的有向图, 以及一对顶点 $s,t$, 如何设计一个 NL 算法判定 $s,t$ 之间没有任何连通路径. 我们可以先把问题简化一下, 再要求输入中给出从顶点 $s$ 出发能到达的顶点个数, 那么我们可以用 NL 算法来验证 $s$ 能到达哪些顶点:

• 如果 $s$ 能到达 $t$ , 直接拒绝;
• 如果 $s$ 能到达的顶点个数跟 $c$ 不一样, 直接拒绝; 否则接受.

顶点个数 $c$ 也可以用一个 NL 算法得到. 考虑顶点集合 $A_i$, 即从 $s$ 出发, 在 $i$ 步内能到达的顶点的集合. 那么我们不难由 $A_i$ 计算 $A_{i+1}$; 于是走了 $n$ 步之后得到的 $A_n$ 中顶点个数就是我们想要的 $c$.

当空间复杂性遇上线性方程组

另外一个重要的问题, 则是确定性的对数空间和非确定性的对数空间的计算能力是否相同, ${\sf L} \overset{?}{=} {\sf NL}$. 一个常见的切入点是 $n\times n$ 的整数矩阵的行列式 (determinant), 可以证明 ${\sf NC^1} \subseteq {\sf L} \subseteq {\sf NL} \subseteq {\sf DET} \subseteq {\sf NC^2}$, 计算行列式需要 $O(\log^2(n))$ 的空间. 如果我们可以找到一个只需要 $O(\log(n))$ 空间的算法, 来计算整数行列式的话, 那么可以证明 ${\sf L} = {\sf NL} = {\sf DET}$.

HHL 算法在量子空间复杂性中的应用

有趣的是, 尽管我们现在仍然不知道如何证明这一结果. 但是如果我们考虑这一问题的量子对应的话, 比如定义类似 ${\sf L}$ 的对数空间的量子复杂性类 ${\sf BQL}$, Amnon Ta-Shma 2013 年在 HHL 算法的基础上, 给出了 $O(\log(n)+\log(\kappa))$ 空间的厄米矩阵求逆算法 ^[3:1], $\kappa$ 是矩阵的条件数 – 也就是说整数行列式计算有对数空间的量子算法!

Fefferman-Lin 后来在 2016 年证明了这一问题是 $\sf BQL$-complete ^[5:1], 并且如果我们定义 $\sf NL$ 的量子对应 ${\sf QMA_{LOG}}$ 的话, 甚至可以证明 ${\sf BQL} = {\sf QMA_{LOG}}$ ^[6]. 既然 $\sf L$ 和 $\sf NL$ 的量子对应是相等的, 那么也许我们可以证明 ${\sf L} = {\sf NL}$? 一个可能的途径是借助今年发展的 block-encoding 等一系列技术, 在此基础上对量子对数空间算法做"退量子化" (dequantization), 那么我们会可能得到低秩 (low-rank) 情形下的随机对数空间算法.

我们能证明 L=NL 吗?

Boix-Adserà, Eldar 和 Mehraban 在最近给出了这一问题的 $O(\log(n)\log(\kappa))$ 空间的经典算法 ^[4:1], 即在条件数为常数的时候对数空间是足够的, 即 $O(\log(n)\log(\kappa))$ 空间的经典确定性算法, 对这一结果的进一部分改进可能会证明 ${\sf L}={\sf NL}$. 他们使用的主要技术之一是 Barvinok 在三年前给出的复多项式插值算法, 这一技术也在积和式 (permanent) 的近似算法中非常重要, 并且和量子计算优越性中的 Boson Sampling 有着很深的联系.

我们不难证明 ${\sf PSPACE}={\sf NPSPACE}$, 因为多项式的多项式仍然是多项式. 但是对数的多项式仅仅是对数多项式, 为了改进到对数, 我们往往需要做一些很复杂的事情 – 譬如经典 PCP 定理中的通信代价, 直接用 low-degree test 把基于 sum-check protocol 的 NEXP=MIP 的证明做 down-scaling, 那么我们可以把多方交互式证明的通信代价从多项式降到对数多项式, 但是更进一步就需要更复杂的技术 (composition). 我们能对对数空间做同样的事情吗? 现在还不得而知.

参考文献