动机
要证明有向图中某个顶点可达,非确定性机器可以猜出一条路径并检查其中的各条边,同时只需保存当前顶点和一个步数计数器。相反的断言似乎更难:一次猜测失败只说明某一条被提议的路径失败了,并不说明所有路径都失败。非确定性机器在至少有一个分支接受时就接受;因此仅仅交换接受与拒绝,并不能得到该语言的补。
令人意外的想法是对在有限步数内可达的顶点计数。一旦知道了正确的计数值,机器就能证明自己已经列出了全部这些顶点,尽管每个正面的可达性证书是逐个检验的。由此得到 。
定义
定义 3.5.1
(非确定性对数空间机器)
非确定性对数空间机器在长度为 的输入上使用 的工作空间;其只读输入带和只写输出带不计入工作空间。若某个计算分支接受,则该输入被接受。我们要求机器在所有分支上都停机。
定义 3.5.2
(可达层及其大小)
对有向图 采用显式的 邻接矩阵编码,顶点编号为 ,并附带合法的源点与目标点下标。其输入长度 满足 ,对数空间机器可以验证该编码,并重新扫描矩阵来检验某条边是否存在。给定源点 ,令
我们把空途径计算在内,故 ,。途径可以重复顶点;这不造成困难,因为我们计数的是顶点而不是途径。每个可达顶点都有一条长度至多为 的简单路径,所以 就是完整的可达集。假设 且源点与目标点是合法顶点;格式错误的图编码可以在主过程之前被确定性地拒绝。
定义 3.5.3
(有向可达性问题 STCON)
有向可达性问题 STCON 询问从 出发能否到达 。它的补问题询问 是否成立。我们使用标准事实:在确定性对数空间多一归约下,STCON 是 NL 完全的。配套的可达性笔记建立了格局图归约。
定理
定理 3.5.4
(归纳计数与不可达性)
有向可达性问题的补属于 NL。因此 。更一般地,对每个空间可构造的界 ,类 对补运算封闭;下面的证明明确建立的是对数空间的情形。
最后这个更一般的陈述只是为了说明背景而提及;其一般的格局计数与空间核算在此不予证明。下面我们不借助该推广来证明对数空间的断言。
命题 3.5.5
(已认证的计数能让一次扫描得出什么结论)
给定正确的值 ,一次有界的非确定性扫描可以在 空间内判定任一指定顶点是否属于 :至少有一个分支能存活,且每个存活的分支都返回同一个正确答案。对所有顶点重复该扫描,即可计算出正确的 ,并具有同样的两条保证。此断言要求所提供的计数是正确的。
证明
以经验证的配额取代存储的集合
机器并不打算把可达集压缩成一个位向量来存储。它存储的是集合的基数,并反复重建对整个集合的证书。这是两种不同的资源: 个顶点的任意子集可能需要 个成员位,而其基数只需要对数多个位。单独的小计数几乎不透露任何信息,但与可靠的正面成员证书结合后就变得很有力。
对每个顶点,选择“不列出”仅仅是一种遗漏,绝不是非成员的证书。选择“列出”则带有出示一条经检验的途径的义务。因此,经检验的列表必然是真实可达集的子集。若它的基数等于该集合已知的基数,它就必须是整个集合。这是一个有限集合的蕴涵,并不是假设非确定性机器能验证任意的否定性陈述。
两个量词必须分开。每一个通过所有检查的存活分支都必须正确;否则哪怕只有一个虚假的接受分支,也会破坏可靠性。而当算法应当继续时,至少有一个分支必须存活;否则,一个正确的断言可能仅仅因为要求所有猜测都去做不可能的事而被拒绝。列出所有真正可达的顶点并附上有效的途径,就提供了第二条性质。这一构造证明了这两条性质,而不是非正式地宣称某个猜出的列表是穷尽的。
推进一个可达层
证明
(逐层推进计数)
首先假设正确的整数 已经存储。我们描述一个有界的非确定性过程来计算 。对每个候选顶点 ,按顺序扫描顶点 。在每个 处,猜测“列出”或“不列出”。若列出,则猜测一条从 到 、至多含 条边的途径,并仅存储其当前顶点、长度和下一个猜出的顶点来验证它。若所声称的某条边不存在,或途径不终止于 ,则立即拒绝。每列出一个 ,就使计数器加一。
在同一次扫描中,若某个被列出的顶点 等于 或有一条指向 的边,则设置一个标志。扫描结束时,除非列出的个数等于已存储的 ,否则拒绝。若通过,则该标志就是“ 是否成立”的正确答案。事实上,所有被列出的顶点都有经验证的见证,且属于 。它们互不相同,因为每个 只被扫描一次。恰有 个成员的 的子集就是整个 。反之,存在一种成功的见证选择:列出 的每个顶点并附有效途径,不列出其他任何顶点。于是等价关系
就证明了该标志的合理性。
统计标志被设置的候选顶点 的个数;这就是 。每次扫描都可能做出新的非确定性选择,但每个通过基数检查的扫描所列出的恰好是 。因此每一个存活的分支计算出的下一个计数都相同且正确。至少存在一个存活的分支,因为每个被列出的可达顶点都存在有效的见证途径。从 开始,对 重复这一过程。
在整个外层遍历过程中,旧的计数必须一直可用。应保留一个单独的累加器来存放下一个计数,并为每个候选顶点 重置局部的“已列出”计数器。只有在每个候选顶点都处理完毕之后,下一个计数才能取代旧计数。若过早复用同一个计数器,后面的候选顶点就会把自己的列表与一个只计算了一部分的量比较,而不是与 比较。这一实现细节是保持归纳不变式的一部分,同时仍然只需要固定个数的小计数器。
正面途径验证者可以选择在长度为零到 之间的任意长度处停止。选择零的分支检查其当前顶点是否已经是所要求的终点;另一个分支则猜测下一个顶点,检查对应的边,并使长度加一。若到达长度上界时仍未到达正确的终点,则拒绝。成员证书之中并不隐藏任何无界搜索。特别地,源点总有空途径作为证书,初始层也不例外。
最后,再对所有 扫描一次,使用长度至多为 的见证以及经验证的计数 。当且仅当扫描存活且没有列出 时接受。若 不可达,则正确的列表给出一个接受分支。若 可达,则每个存活的列表都包含它,其余分支全部拒绝。这就在两个方向上证明了正确性。
在任一时刻,机器存储 、当前的 与 、当前途径的顶点与长度、若干不超过 的计数器、当前计数 以及若干标志。每一项都需要 位。矩阵输入可以重新扫描以检验某条边,且不保留任何顶点列表或路径。循环与见证长度都有界,因此每个分支都会停机。显式编码满足 ,所以这是 空间。简洁的图编码相对于其输入长度可能有指数多个顶点,需要另行分析;本证明不涵盖这种情形。
证明透视
基数检查为何承担整个论证
层推进能够成功,靠的是两点。第一,“恰好列出 个互不相同且经验证的顶点”这项检查,把正面证书变成一份穷尽的列表: 的一个含 个元素的子集就是 本身,所以每个存活分支上的标志都正确,而列出全部 又说明存活分支必然存在。第二,正确性是逐层继承的:所存储的 正确这一假设在每一层都会用到,它之所以成立,是因为上一层的所有存活分支都算出了正确的计数,并由 开始。旧计数必须在新计数累加期间保持不变;过早覆写会把列表与错误的数字比较。没有可信的计数,这项检查就什么也证明不了,配额例子正说明了这一点。
证明
(从不可达性到 coNL)
要从不可达性推广到整个 coNL,设 ,并设 是到 STCON 的确定性对数空间归约。则 恰好当 是一个不可达性实例。对数空间机器可以在 的虚拟输出上模拟不可达性算法,在需要时重新计算被请求的输出位,而不是存储整个图。于是 ,即 。取补即得相反的包含关系。
对于通常的停机的对数空间转换器,这一模拟只有多项式多个虚拟输入位置:否则,重复出现的内部格局会永远重复下去,而输出带又不能被读取以改变后续行为。因此,要获得某个被请求的输出位,只需用一个位置计数器重新运行该转换器。同时保存该计数器与不可达性机器的各条工作带,相对于原输入长度仍然只用对数空间。这就是为什么对数空间归约下的封闭性不需要把它们的整个输出实体化出来。
例题详解
例题 3.5.6
(分层统计可达顶点)
取顶点 与边 ,,,源点为 。则 ,,。计数依次为 。对于阶段 的候选顶点 ,一次扫描必须列出 的三个成员并附上见证。边 使标志被设置。只列出 和 的扫描不可能错误地把 判为不属于:它通不过计数检查。
例题 3.5.7
(含圈的不可达目标)
设图的边为 和 ,另有孤立顶点 ,源点为 ,目标点为 。前两个可达集是 和 ;此后的可达集都保持为 。尽管绕圈的途径有无穷多条,但每个可达顶点的最短见证至多含一条边。一次有效的最后扫描列出 而不列出 ,因此某个分支会接受不可达性。
例题 3.5.8
(未经检验的较小配额可能隐藏可达顶点)
取五个顶点,源点为一,边为 ,,。在第一层,真实的可达集是 ,其计数为三。在检验四是否属于下一层时,只列出一和二的扫描具有有效的正面证书,却遗漏了前驱三。在正确的配额下,它因只列出了两个而非三个顶点而被拒绝。若允许机器没有理由地猜测较小的配额二,同一次扫描就会存活,并错误地报告四不属于。逐层的构造通过让每个配额都源自其经认证的前一个配额,排除了这种情形。
常见错误
常见错误
(猜测的计数不是经认证的计数)
猜测出来的计数本身不可信。该过程从已知值 出发,并利用前一个正确的值来验证下一个计数。同样,也不能简单地猜测某个未被列出的顶点不可达:基数检查迫使每个存活的扫描都包含所有可达顶点。
常见错误
( 并不给出 )
并不蕴涵 ;它给出的是补问题的非确定性算法,而不是确定性算法。
反例模式
重复计数同一顶点会使配额失效
设扫描可以把同一个顶点列出多次,而只把经验证的声称的个数与 比较。取五个顶点,源点为 ,边为 ,,,则 ,。一次扫描把顶点 列出两次、顶点 列出一次,共作出三个经验证的声称,各有有效的途径( 用空途径, 用边 ),因此通过计数检查。它从未列出 ,所以没有被列出的顶点有边指向 , 的标志保持未设置。于是该扫描报告 ,但 是一条长度为二的途径。按递增次序、每个顶点至多列出一次,则经验证的声称构成一个集合,而 的含 个元素的子集必然是整个 。
总结
正面的路径证书加上一个已经认证的计数,就能迫使得到一个穷尽的列表,而无需存储它。对相继的路径长度上界重复这一观察,就证明了有向不可达性属于 NL。这一结果是关于非确定性对数空间算法的存在性陈述;它并没有给出有向可达性的确定性对数空间算法。
练习
快速检查
(对于边 ,,, 以及孤立顶点 ,以 为源点,求 ,并判定目标点 是否可达。)
逐层建立 。
解答 · 答案
可达集依次为 ,,, 和 ,计数为 。顶点 不可达。
快速检查
(为什么验证扫描只需对每个顶点处理一次?如果同一个顶点被重复计数,会出什么问题?)
比较声称的个数与互不相同的顶点个数。
解答 · 答案
每个 只处理一次,使得经验证的声称的个数就是一个集合的大小。若允许重复计数,则同一个可达顶点可能被多次列出,从而凑满配额,而另一个可达顶点却被遗漏。
快速检查
(某位同学声称,在对 个顶点完成一次扫描后,没有找到通向 的路径就证明了不可达。指出缺失的条件。)
某个分支可能根本没有列出某个顶点。
解答 · 答案
某个分支可以选择不列出一个可达顶点,或者猜出错误的见证。扫描必须验证每一个正面声称,并验证被列出的互不相同的顶点个数等于已认证的正确可达计数;否则遗漏 什么也证明不了。
快速检查
(在只有一个顶点、且源点与目标点都等于该顶点的图中,不可达性应当接受吗?请解释零长度的情形。)
空途径算不算途径?
解答 · 答案
不应接受。空途径表明源点可达自身,所以 包含目标点。由于 ,最后的列表是 ,每个有效分支都会拒绝不可达性。
快速检查
(若 ,且 在确定性对数空间多一归约下也是 NL 难的,证明 在同类归约下是 coNL 难的。)
从任意的 出发,取其补语言。
解答 · 答案
设 ,即 。由 NL 难性,存在确定性对数空间函数 ,使得 当且仅当 。取补得 当且仅当 。因此每个 coNL 语言都可归约到 。