前一空间单元定义了对数工作空间并证明有向可达性属于 NL。本单元通过构造格局图证明相应的难度结论,再用确定性的中点搜索代替非确定性猜测。配套的 Savitch 单元证明一般模拟及下文使用的归约复合引理。
为什么有向可达性是 NL 完全的
定义 3.4.1
(对数空间多一归约)
对数空间多一归约在一条只写输出带上计算其输出,同时只使用对数大小的工作空间。输出可以是多项式长度:输出带上的单元不计入工作空间的界。正是这一区别使得下面的构造成为可能。我们将一次一条边地生成图的描述,而不是在内存中保留这个图或广度优先搜索的标记。
定理 3.4.2
(有向可达性是 NL 完全的)
在对数空间多一归约下,对于有向图的标准显式编码,有向可达性对 是完全的。
证明
(NL 难度的证明)
属于 的结论已在前一空间单元通过猜测一条长度至多比顶点数少一的路径而得到证明。关于难度,设 ,并固定 的一个采用标准单侧工作带模型的非确定性对数空间判定器 。长度小于二的有限多个输入可分别映到硬编码的可达或不可达实例。它的状态集和工作带字母表都是固定的常数。选取一个整数常数 ,使得对每个长度 的输入,该机器至多访问 个工作单元。对于输入 ,用一个状态、输入头位置、工作头位置以及这 个单元的内容来定义一个格局。候选格局至多有
个。该上界包含了不可能出现的组合;这不会造成问题,因为只有从真正的起点可达的格局才会影响答案。离开保留的工作带窗口的转移被省略:空间界保证从真正起始格局出发的分支不需要这样的转移。
给每个候选格局赋予一个互不相同的、由 个比特构成的数值标号。输出一个以这些候选格局为顶点、另外再加一个全新的汇点的图。当且仅当 在固定输入 上的一次转移将 变为 时,存在从 到 的弧。从每个接受格局向这个全新的汇点添加一条弧。省略自环不会改变到该不同汇点的可达性,因此输出可以是不含自环的简单有向图。令源点为初始格局,目标为这个全新的汇点。 的一个接受计算就是从源点到汇点的一条途径(walk)。反过来,每条从源点到汇点的途径都遵循合法的转移,直到到达一个接受格局,因此它描述了一个接受分支。于是, 当且仅当输出图中存在一条从源点到汇点的路径。
还需要论证资源界,而不是仅仅指出该图的规模是多项式的。使用两个 比特的计数器枚举候选标号的有序对。把每个标号解码为一个状态、若干头位置以及一个长度为 的工作带字,这两个被解码的格局都能放入 的工作空间。为了检验一个给定的转移,扫描只读输入至输入头所指定的位置,并将这些格局与固定的转移表进行比较。在只写输出带上打印相应的邻接矩阵比特,并为下一对重复使用相同的单元。候选格局的个数与边的个数都是多项式的,所以该过程在多项式时间内终止。初始格局和接受格局在同样的工作空间界内即可识别。因此,该图及指定的顶点是在对数工作空间中产生的,这证明了 可归约到可达性。
证明透视
格局图归约依赖什么
所构造的图包含每一个语法上有效的元组,无论它是否出现在真实计算中,而证明只需要两个事实。可靠性由对路径长度的归纳得出:源点是真正的起始格局,每条边都是合法转移,所以从源点可达的每个顶点都是确实会出现的格局,图中其他位置的虚假元组不可能位于从源点出发的路径上。完备性只用到一次空间界:从真正起点出发的每个分支都留在 个单元格之内,所以截取窗口时没有丢掉任何需要的转移。汇点是全新的,每个接受格局恰好贡献一条新边,因此 接受等价于可到达汇点。资源界则是关于生成器的另一个论证,而不是关于图本身。
正确性与空间分析回答的是不同的问题。仅仅存在一个多项式规模的图是不够的:归约必须能够用对数大小的工作内存枚举出它。反过来,只写输出带并不是一个归约之后可以重新读取的隐秘存储库;该构造在需要信息时会重新计算或重新枚举这些信息。一旦得到 NL 难度,下面的平方对数可达性算法就蕴含 ,这使用的是配套单元中证明的对数空间归约复合模拟;该单元也证明了更强的一般 Savitch 定理。
确定性的对数平方空间算法
前一单元在猜测路径时用到了非确定性。我们现在以二次对数的代价消除它。
定义 3.4.3
(有界长度的可达性)
对于顶点 和整数 ,记 为如下陈述:存在一条从 到 的、至多有 条边的有向途径。
命题 3.4.4
(可达性的确定性空间)
对于有 个顶点的图,有向可达性可以由使用 工作空间的确定性算法判定。
证明
(证明)
定义 恰好在 或 是一条边时成立。对于 ,我们断言 成立当且仅当存在顶点 使得 与 成立。若这样的 存在,把两条途径连接起来就得到一条至多有 条边的途径。反之,取一条从 到 的、有 条边的途径,并令 为其经过 条边之后的顶点。前一部分有 条边,后一部分有 条边,因为由 得 ,而 是整数。当 时有 ,取 。
令 ,所以 。由上一命题中的简单路径论证, 从 可达当且仅当 成立。递归地计算 :对 直接检查输入,对 则按顺序遍历所有顶点 ,先检验 再检验 ,并在第一次成功时接受。每个栈帧存储 、、循环变量 以及层级 。这就是三个各占 比特的顶点名称,再加上层级所需的 比特。递归深度为 ,已结束的子调用的栈帧被丢弃并重复使用。总的工作空间为 ,外加读取输入所需的指针。
这就是 Savitch 定理中节省空间的机制。当递归从途径的前半部分转到后半部分时,它重复使用了前半部分所占的内存。代价是时间:每一层最多进行 次递归调用,因此调用次数至多为 ,这是拟多项式而非多项式。
例题 3.4.5
(四顶点路径上的中点递归)
设顶点为 ,边为 、、,于是 ,。为了计算 ,算法依次尝试中点 。对于 ,调用 成立(取其自身的中点 ),但 不成立:它需要一个中点 ,使得 与 各有至多一条边的途径,而这样的 不存在。对于 ,我们需要 与 。第一个以中点 成立,因为 为真,且由于 是边, 为真。第二个以中点 成立,因为 与 是边。所以 为真,这与唯一的三条边的途径 相符,而三不超过 。对于反向查询 ,没有任何中点可用,因为顶点 没有出边,所以从 出发的唯一途径是空途径;算法在穷尽全部四个中点之后正确地回答否。
常见错误
(对数平方空间并不意味着快)
当 很大时,上述递归使用的内存远少于标记数组,但它多次重复同样的子问题。内存很小的过程可能运行拟多项式时间,而像广度优先搜索这样的多项式时间搜索则可能使用线性内存。两种界都不蕴含对方,这就是必须分别追踪这两种资源的原因。
反例与界的紧性
前述结果中的每个假设都有其理由,下面的例子说明缺少它会出什么问题。
反例模式
路径长度的界 n-1 不能再降低
一个诱人的说法是:至多含 条边的途径已足以判定可达性。在顶点为 、边为 的有向路径图中,从 到 的唯一途径恰好有 条边,所以一台在仅仅 条边之后就拒绝的机器,会错误地拒绝这个属于语言的实例。因此界 是紧的。
计数器不能省略。在边为 与 且 不可达的图上,没有计数器的机器有一条在 与 之间永远交替的分支。该分支永不停机,违反了所有分支都停机的约定。计数器保证了这台特定的机器在该约定下是一个判定器。
反例模式
对数空间不是对数时间
一个诱人的说法是:使用对数工作空间的机器也在对数时间内运行。考虑 上仅由 组成的字符串的语言。它可以用常数工作空间通过一次扫描来判定。然而没有任何确定性机器能在 上以少于 步判定它。从左端点标记出发,输入头至少要经过 步才能到达单元格 。如果机器在少于 步内停机并接受 ,则某个单元格 从未被读取。把该单元格改成 不会改变计算,于是机器也会接受一个不在语言中的字符串,矛盾。
对于更大的空间界,格局计数并不给出多项式时间。一台在二元字母表上使用 个工作单元格的机器可以有 种不同的内容,因此同样的论证只给出指数时间的模拟。这与 和 之间尚未解决的关系相一致,并不与之矛盾。
概念视角算法
同一条路径的两种资源度量
可达性过程保存一个顶点和一个计数器,再反复扫描输入以验证每条猜测的边。计数器把一个分支限制在简单路径的长度以内;空间则衡量搜索期间重复使用的存储单元。因此对工作空间的对数上界,并不意味着计算步骤也只有对数个。
将归约视为算法
完全性证明从一台固定的机器 出发,并把它的输入 作为归约的可变输入。固定 是关键的:它的状态集、字母表和转移表都具有常数大小,尽管编码后的格局以及所得到的图会随 增长。NL 中的另一个语言可能需要另一台机器,因而需要另一个归约;完备性并不保证存在同时表示所有机器的某一个图。
归约有两项任务。答案的等价性是关于输出图中路径的数学陈述。空间界则是关于生成该图编码的过程的陈述。对于邻接矩阵,生成器遍历所有标号的有序对,并输出一个比特。它可以重新访问输入,并对每一对标号重新计算一次转移检验。打印出的比特数,以及打印这些比特所用的时间,都不等同于同时被占用的工作单元数这一资源。相反,若把整个矩阵存放在工作带上,就会破坏所声称的空间界。
例题 3.4.6
(一个很小的格局图)
考虑一台非确定型机器,其初始格局 有两个合法的后继:一个拒绝格局 和一个接受格局 。假设两者都停机。归约产生顶点 以及一个新的汇点 ,边为 、 和 。路径 见证了接受,尽管另一条分支是拒绝的。若删去边 且不添加其他转移,则 不可达,所有分支都拒绝。该图表达的是存在性接受,而不是各分支之间的多数表决。
例题 3.4.7
(中点检验中的空游走)
设图有顶点 和唯一的一条边 。在第零层, 为真,因为空游走的长度为零; 为真,因为该边存在。因此在第一层,取 即可证明 。对于 ,两个候选都不成立: 要求 ,而 要求同一个为假的陈述。允许长度为零的片段,正是使该递推式无需添加人为自环就能处理短于其上界的路径的原因。
中点方法并不会仅仅因为每个存储的标号很短就构造出多项式时间的判定过程。它在每一层都遍历候选中点,并反复重新计算子问题。工作带的分析只跟踪一条活跃的递归调用链,而时间分析则要计入依次发出的大量调用。这一区别说明了为什么该递归可以节省内存,却不能由此判定 NL 是否等于 L。
补充练习与解答
快速检查
(对于递归可达性算法,分别对 和 计算递归深度以及每个栈帧所存储的顶点比特数。)
解答 · 答案
对于 ,,所以有 层,标号为 的顶点各需 个比特。每帧三个顶点花费 个比特,五个栈帧共花费 个比特用于顶点。对于 ,,得到 层,标号为 的顶点各需 个比特。每帧三个顶点花费 个比特,六个栈帧花费 个比特。从 跳到 ,是因为当 越过 的幂时,深度和栈帧宽度都增加了。
快速检查
(对于上面删去转移 后的机器,在其格局图中添加边 ,同时保持 为拒绝的停机格局。所得的图从 出发会给出正确答案吗?请说明理由。)
解答 · 答案
不。添加的边断言拒绝的停机格局可以一步到达接受,而机器并没有这样的转移。这产生路径 ,但修改后的机器没有接受分支。图中必须恰好只含有从接受格局出发的通向汇点的边。
快速检查
(在顶点为 、仅有边 的图中,确定 和 。)
解答 · 答案
为真,因为空游走使用零条边,不超过 。 为假:没有边离开 ,所以从 出发的唯一游走始终停留在 。
快速检查
(某归约使用对数大小的计数器打印出多项式长度的输出。为什么仅凭输出长度并不与其工作空间界相矛盾?)
解答 · 答案
在该归约模型中,输出带是只写的,不计入工作空间。生成器可以输出每个符号并重复使用其计数器;它之后不能把输出带当作可读的存储。对数界针对的是同一时刻所使用的工作单元数,而不是最终打印出的符号总数。