理论计算机科学基础随堂笔记。第8章-3：NL完全、NL=coNL
使用教材：《计算理论导引》（原书第3版） Michael Sipser 著，机械工业出版社
第8章-3 格局图与有向路径问题PATH
之前在8-1.3 对数空间中已经给出了对数空间图灵机（对数空间图灵机）的定义。下面对格局图作进一步的说明：
格局图有如下特征：
- 以格局作为顶点的有向图
- 在一步可达的格局之间连边
- 初始格局$c_{start}$、接受格局$c_{accept}$都是唯一的
有了格局图，我们就可以把接受性问题转化为有向图路径问题。
8-1.3节还给出了两个重要的结果：
- 设$f(n)$空间的图灵机有c个状态和g个带符号，那么它的格局图就有$n2^{O(f(n))}$个顶点，因此每个格局的长度为$\log n+O(f(n))$。所以对数空间图灵机（即$f(n)=\log n$）格局的长度为$O(\log n)$。如果只需要记录常数个格局（即记录局部运行时信息），那么使用对数空间图灵机就可以做到，空间复杂度为$O(\log n)$。
- $PATH\in NL$。
另外，$PATH\in P$，这是因为我们可以设计一台图灵机，对于输入$\langle G,s,r\rangle$，它从$s$出发，逐个标记它能到达的顶点，利用洪水标记算法的思想，就可以确定从$s$出发最终能否到达$t$。
总结一下，关于PATH，我们有
- $PATH\in P, L$
- $PATH\stackrel{?}{\in} L$
- $UPATH\in L$（它的证明比较困难，用到了很多精巧的数学技巧）
8-3.2 对数空间归约
对数空间归约，记作$\leq_m^L$，定义如下：
如果$A\leq_m^L B\ \ via\ \ f$，那么$x\in A\Leftrightarrow f(x)\in B, f\in FL$。这里FL指的是对数空间可计算函数类，即对数空间图灵机可计算的函数。
对数空间归约具有传递性。为了证明这一点，只需要注意输出带不要输出全部结果再送给下一台机器，而是一遍输出一边让下一台机器计算，这样可以保证两台机器加起来的存储空间仍然是对数空间。
对数空间归约具有封闭性。即，设$X$代表$L, NL, coNL$之一，则：$A\leq_m^L B, B\in X\Rightarrow A\in L$。
8-3.3 NL完全问题
关于L, NL, coNL之间的关系，有
\[L\stackrel{?}{\subseteq} NL=coNL\]L与NL是否相等还未知。
下面证明$PATH$是NL完全的。
首先，$PATH\in NL$。这在8-1.3 对数空间 例3中已证明。
其次，任意NL类的语言都可$\leq_m^L$归约到$PATH$上：
$\forall A\in NL$，存在对数空间NTM M，$A=L(M)$。设输入$w$的规模（长度）为n，则M的格局长度为$c\log n$。构造M在$w$上的格局图$G$和顶点$s,t$如下：
- G的构造
顶点的构造：枚举所有长度为$c\log n$的串，如果是合法格局则加入到$G$的顶点集中；
边的构造：枚举所有格局对，如果满足转移函数一步可达，则输出作为边。
- $s,t$的构造
s为初始格局$c_{start}$，t为接受格局$c_{accept}$。
这样的构造只需要占用$O(\log n)$的空间，因此是对数时间归约。■
推论 $NL\subseteq P$。
证明：$PATH$是NL完全的，$PATH\in P$，$P$类在$\leq_m^L$下封闭。因此$NL\subseteq P$。■
还有更多NL完全问题，如$A_{NFA}, E_{DFA}$等。
8-3.4 NL=coNL
确定性复杂性类（如L, P, PSPACE, EXP等）对补运算封闭，非确定性复杂性类则要分别讨论。对于非确定性时间复杂性类（如NP与coNP），其封闭性仍未知（猜想NP≠coNP），而非确定性空间复杂性类对补运算封闭，例如$NSPACE(f(n))=coNSPACE(f(n))(f(n)\geq \log n)$。本节将要证明，$NL=coNL$。
这个结论似乎是违背直觉的，这也说明复杂性领域内相当多的问题仍有许多空白。
回顾NP的两个定义：
- 非确定性多项式时间可判定，即$A\in NP\Leftrightarrow\exists\ NTM\ M, M用O(n^k)时间判定A$；</br>
- 确定性多项式时间可验证，即$A\in NP\Leftrightarrow A=${$x\mid \exists^p y,\langle x,y\rangle \in C$}，其中$C\in P$类。
我们可以类似地给出NL的两个等价定义：
- 非确定性对数空间可判定，即$A\in NL\Leftrightarrow \exists\ NTM\ M, M用O(\log n)时间判定A$；</br>
- 确定性对数空间只读一次可验证，即$A\in NL\Leftrightarrow A=${$x\mid \exists y, \langle x,y\rangle \in C$}，其中$C\in L$类，且只读一次y。
称$y$为$x$的只读一次(短)证书。
疑问：为什么要只读一次呢？
下面证明$NL=coNL$：
证明：之前已经证明$PATH$是NL完全问题，因此只要证明$\overline{PATH}\in NL$即可。