引言
这一小篇内容主要围绕 \(NL = coNL\) 的证明展开，不过我更想强调的是一些概念上的辨析，也就是题目里说的非确定图灵机的补问题的构造。这篇内容不涉及科普计算理论和复杂度理论中内容的形式化定义，阅读需要自备相关的知识基础。本文更多的是对自己学习时的思考过程，否定之否定的一个记录备忘，因此行文会比较意识流。
P = coP
首先关注确定性图灵机定义的复杂度等级。对于任意这样的复杂度，比如 P，EXP 等，都可以证明其补问题复杂度和原问题同级，也即 P＝coP，EXP = coEXP。因为确定性的图灵机的补很容易改造，只需要套一层壳就行了。比如，对于任意问题 \(x\in P\)，我们有多项式时间判定该问题的图灵机 \(M_x\)，那么我们只需要构造新的确定性图灵机 \(\bar{M_x}\)：输入 w，使用 \(M_x\) 判定，若接受则拒绝，若拒绝则接受。因为原来的图灵机是多项式时间复杂度，而新构造的图灵机只多了一步，因此仍然是多项式时间复杂度，则 \(P\subseteq coP\)。根据下面的命题，我们得出 \(P=coP\)。
命题：对于任意复杂度级别 \(\Gamma\)， 如果 \(\Gamma\subseteq co\Gamma\) 或 \(co\Gamma\subseteq \Gamma\)，则必有 \(\Gamma=co\Gamma\)。这一结论非常明显，考虑任意问题 \(\gamma\in \Gamma\)，不失一般性，假设第一个条件成立，也即 \(\forall\gamma \in\Gamma\rightarrow\bar\gamma\in \Gamma\), 考虑到这一命题里 \(\gamma\) 只是个哑标，我们取成 \(\gamma = \bar\delta\)，也即 \(\forall\bar\delta\in\Gamma\rightarrow\delta\in\Gamma\)，这一命题恰好说的就是 \(co\Gamma\subseteq\Gamma\)，因此 \(co\Gamma=\Gamma\)。
非确定图灵机的行为
直观上理解，非确定图灵机 （NTM）像是拥有无限的计算节点，可以在每一步进行分叉，但是任意分支之间不共享内存（纸带独立，总是继承自上一步），不能通讯（没有中心节点调度，各分支完全无法共享结果或者汇总结果）。除此之外，最重要的一点，根据非确定图灵机的形式化定义，其结果是 OR，也即任意分支接受，则图灵机整体接收，反之，只有所有分支全部拒绝，图灵机才会拒绝。这种 OR 行为，是不能更改的，来自于非确定性图灵机的形式化定义，也是唯一的对于不同分支的类似“汇总”的合法操作。其他任何尝试对比汇总不同分支的结果，哪怕只是把非确定图灵机的 OR 行为改成 AND 都是不被允许的。
被 NTM 定义的复杂度名称，一般以 N 开头。需要注意 NTM 并没有任何现实的计算设备与其类似，因此只是用来严格化复杂度理论的数学工具。
NP?＝coNP 一个错误的理解
\(NP = coNP\)，类似 \(P＝NP\)，是一个还没有解决的问题，同样大多数人相信 \(NP\neq coNP\)。但是乍一看，似乎 \(NP=coNP\) 是显然的，就如同我们证明的 \(P=coP\) 一样。一个可以暂时安慰自己其不显然，但实际上不正确的理解是这样的：一个解决 NP 的 NTM 只是有一个分支可以在多项式时间接受，不代表其他分支也在多项式时间拒绝。因此取该 NTM 的补时，我们可能需要等比多项式更长的时间，才得到所有的拒绝，因此 NP 可能不等于 coNP。
后面我们将看到这个理解是错的，因为这种图像解释不了为什么 NL 和 coNL 不是平庸相等的（虽然两者确实是相等的）。这个理解错误的地方就在于，我们无法构造一个 NTM 给出指定 NTM 相反的答案。也即回到了题目，非确定图灵机的补是无法有效构造的。
几个反转 NTM 的尝试
如果还是不信邪，就看几种常见的反转想法。
- 将每个分支的结果反转。考虑之前有一个分支接受，其他拒绝，NTM 的结果是接受。反转之后，一个分支拒绝，其他接受，NTM 的结果还是接受！！！因为 NTM 是分支逻辑 OR，只要有一个分支接受就接受，所以反转所有分支不对应反转 NTM。
- NTM 套壳，用另一个 NTM 模拟 NTM，最后反转该 NTM 的输出。漏洞： NTM 无法被套壳，因为其本质逻辑就是分支再分支，这些分支是不会有任何收束的，每个分支的运算不知道其他分支的存在，唯一可以定义在 NTM 上的跨分支操作，就是最后那个 OR，因此任何尝试分支之后再做些什么的想法，都已不是 NTM。因为分出的支就是泼出的水，再也没机会看到其他分支的事情。
NL-completeness
NL 和前述不同，是一个关心空间复杂度的命题，具体的是指 NTM 只需额外使用对数数量级的空间就能够判定的语言（或问题）。由于纸带上每个变量就占对数空间（比如 base 2），所以 NL 几乎就是说只需要常数个额外参数就能解决的问题（在 NTM 上）。NL 完全问题，则定义为那些任意 NL 问题都可以在对数空间约化到的问题（不是多项式时间，每一复杂度的完全问题定义，对约化的限制与之匹配才有意义）。
我们可以证明 PATH 问题是 NL 完全的，PATH 问题指的是给定图 G，和起点 s，终点 t，存在一条从 s 到 t 的路径。这一问题是 NL 很容易，只需 NTM 分支猜节点连续 \(\vert G\vert\) 步即可，其中任意分支出现 t 则接受，否则拒绝。需要注意每一分支只保存步数和现在节点两个量即可，因此使用了对数空间。
而证明 PATH 是 NL 完全的，需要将任意 NL 问题（M 识别 w）约化到 PATH。约化方法就是构造图 G，使得每一个节点都是 M 识别 w 的可能状态（包括M的状态，M两个指针的位置和工作带内容，这些内容可以证明都不超过对数空间，其实都是一些常数）。而每一条有向边，指的是两节点间的转换符合图灵机的定义，生成这些边的过程所需的额外空间也是对数量级。由此设 s 为初始状态，t 为终止状态（如果本来 M 有多个终止状态，可以改造为移动到统一状态），因此在 G 上找到一条路径从 s 到 t，完全等价于 M 识别 w，PATH 是 NL 完全，证毕。
NL = coNL
定义 \(\overline{PATH}\) 是 \(PATH\) 的补问题，也即给定图和起点终点，没有路径相同的问题集合。显然该问题在 coNL，因为 PATH 本身是 NL。如果我们能够证明该问题本身也在 NL。那么根据 NL 完全的定义，任意 NL 问题 \(x\in NL\)，存在占据对数空间的 f，\(s.t. \omega \in x \iff f(\omega)\in PATH\)。此时补问题 \(\omega\notin x \iff f(\omega) \in \overline{PATH}\)。由此可见补问题 \(\bar x\) 的解决可以通过 \(\overline{PATH}\) 的解决，也即 \(NL\subseteq coNL\)。由第一节的命题， \(NL=coNL\)。因此欲证明 NL＝coNL，只需证明 \(\overline{PATH}\in NL\)。
我们先看一下，为什么两者不是显然相等的。如果我们还抱着 NTM 套壳的错误理解的话，我们就会发现二者显然相等。因为每个分支只需尝试顶点数目 m 步，而所有过程空间都被对数限制住，不存在 NP 的 NTM 中拒绝分支可能时间超出多项式级的问题，因此只需将 PATH 的 NTM 套壳反转，我们就证明了 \(\overline{PATH}\in NL\)。面对教材给出的更长证明，在读懂证明前，我花了更多的时间纠结为什么上述证明不行，这也成就了本文的整个上半部分：如何理解 NTM 的反转是做不到的。
正确证明
最后我们简述一下 NL ＝ coNL 的正确证明，以更好的理解 NTM 的行为和微妙之处。
先看一个简单的问题，如果我们的输入除了 G,s,t 之外，还包括一个数字 r，r 表示从 s 出发可以到达的节点的总数目，那么我们提出一个 NL 的算法，来给出不存在 s 到 t 路径的判定。（假设顶点总数为 m）
每个分支维持一个计数变量 c，每个分支选择 G 中的一组节点来依次测试，对每个节点测试时再依次分支，测试 m 步之内的所有路径，如果 m 步结束对应顶点为测试顶点则继续，否则拒绝。如果任意测试过程，碰到 t 顶点，则拒绝。该组顶点全部通过测试的分支，如果此时计数变量 c＝r （每测试一个顶点，c加1），则通过。总结起来，该 NTM 的作用就是如果能找到一组共 r 个节点 （c=r 保证），且其中不含节点 t （遇到 t 的分支直接拒绝保证），且 r 个节点都从 s 可达 （测试过程保证），那么因为一共有 r 个节点 s 可达，则 t 节点 s 不可达，也即无路径存在，通过。
写成伪代码，则为
/* input G,s,t,r, r is the number of vertices that s-reachable */
c = 0
for v in G - t
non-deterministically assign guess to v /* for every branch, this means choose a set of vertices and guess them in the set s-reachable */
if guess = True
p = s
for i = 1 to m
non-deterministically pick a neighbor of p or p itself as q /* for every branch, equivalently trying all path with length less than m from s, and if v is s-reachable, then there is at least one branch with p_m = v */
p = q
if p = t
reject
if p != v
reject
c = c + 1 /* count how many vertices are s-reachable */
if c = r
accept /* find all r vertices s-reachable and no t in them, hence accept */
else
reject
要注意 NTM 是伪代码的不确定性的体现，如何阅读与理解是和普通算法有区别的。这段代码，代表每个分支要做的任务。每次以 non-deterministically 开头的行，就表示 NTM 要进一步分支。这一算法每一分支只需维护一个计数器 c 和前任顶点 p，因此仅需对数空间。
现在我们只需设计一个 NTM 算法，使得某一分支可以得到正确的 r 值，其他分支被拒绝，然后在该分支上继续上述的算法，即可决定 \(\overline{PATH}\) 问题。
我们先列出算法如下。
/* input G,s,t*/
r_0 = 0 /* r_i is the number of vertices that s-reachable in at most i steps */
for k = 1 to m /* find number of vertices in s-reachable in i steps */
r_{k} = 0
for all v in G /* judge whether v is in k-step s-reachable*/
d = 0
for all w in V /* loop on w to find all vertices s-reachable in k-1 steps */
non-deterministically assign guess to w
if guess = True
p = s
for i = 1 to k-1
non-deterministically pick p itself or a neighbor of p as q
p = q
if p != v /* p is now a vertex k-1 step away from s */
reject
d = d + 1 /* count how many vertices in s-reachable in k-1 steps */
if v is a neighbor of w or v = w
r_{k} = r_{k} + 1 /* count how many vertices in s-reachable in k steps */
break w loop /* enter next loop of v, to determine next vertex */
if d < r_{k-1}
reject /* force find all vetices in s-reachable in k-1 step, such that the newly find set in k step is full */
/* after the computation on r_m, keep the algorithm in the first code block, with r_m here as the r input */
首先，以上算法只会在纸带上记录 \(w,v,r_{i-1},r_{i}, d, i\)，所以是对数空间。这一算法利用了 s-reachable in k step 的概念，也即对应顶点从 s 点出发可以在 k 条边以内到达。而 0 step 对应 s 点本身，由此可以递推归纳下去，和 k step 点有邻边的点都在 k+1 step 集合之中。
这一算法为了保证使用空间足够小，所以每次从 s-reachable in k step 来递推寻找 s-reachable in k+1 step 时，要重新复现 k-step 可达的顶点，相当恐怖地利用了以时间换空间。还有一个要注意的点就是最后验证 \(d=r_{k-1}\) 很重要，否则会有分支找到 k-step 可达的真子集并继续进行算法，使得这一部分算法结束时出现最后的不同分支 r 不一致的情况。这也是为什么不能一次到位，直接用 m 步 NTM 分支来锁定 s 可达顶点的数目，因为其结果不相同，可能对应分支只是 s 可达顶点的子集。而真实结果是所有分支中的最大值，但注意到我们无法比较 NTM 不同分支的值，因此只能用上面这个迂回的算法。
为了更直观的理解该算法，让我们看一下，算法的求 r 部分，最多可能有多少分支。对于判定每一个 v 是不是在 k-step 可达，我们都需要重构出 (k-1)-step 的集合。而这一重构过程的验证，需要分支出所有不大于 k-1 步的路径来依次判断 (k-1)-step 中的每个元素。因此需要的分支是 \(O(m2^mmm^m )\)。分支总数相当暴力，但我们只要把空间控制在常数个变量，对数数量级即可。
证毕。
Reference
- Introduction to the Theory of Computation, Michael Sipser.
- 形式语言与自动机理论，蒋宗礼，姜守旭。
- Some enlightening posts on stackexchange:
- https://cs.stackexchange.com/questions/10485/flaw-in-my-np-conp-proof
- https://cs.stackexchange.com/questions/21613/why-cant-we-flip-the-answer-of-a-ndtm-efficiently
EOF