算法在一次计算结束后可以重复使用内存,而已经花费的时间却无法收回。空间复杂度度量的正是这种可重复使用的资源。一台小空间的机器仍然可以运行很长时间,这一差别在图的可达性问题中清晰可见。
为什么空间需要单独计量
在前面的各单元中,核心资源是计算步数。时间是一种累积性资源:每执行一步,都会被永久计入这次计算。内存的行为则不同。曾保存过中间值的工作带单元格可以被覆写,因此同样的少数几个单元格可以服务于成千上万次相继的子计算。因此,一个按其执行步数来计算显得代价高昂的过程,若按其在任一时刻所需的不同存储量来计算,可能只需很少的空间。
本单元有三个目标。第一,固定一个即使在线性规模以下也有意义的空间模型,这要求对输入采用一种谨慎的约定。第二,证明判定有向图中一个顶点能否到达另一个顶点这一基本问题,可由只有对数工作空间的非确定性机器求解。第三,将空间与时间以及确定性空间联系起来:我们证明非确定性对数空间包含于多项式时间,并陈述可达性可在对数平方空间内被确定性地判定;该证明见另一配套续篇。这些证明依赖于贯穿本单元的同一个思想,即内存很小的机器只可能处于数量很少的不同情形,并且这一限制可以被精确地计数。
图的可达性是合适的检验案例,原因有三。它是一个定义清晰的自然问题。它的显然算法,例如广度优先搜索,使用的标记数组所需空间与顶点数成线性关系,因此对数界是真正的改进,而不是簿记上的技巧。并且它的表达能力足够强,如下文所述,它能刻画整个类 。
度量空间
定义 3.1.1
(空间类)
使用一条只读输入带和一条单独的可读写工作带;空间是工作带上被访问过的单元格数。 是由在长度为 的输入上使用 工作空间的确定性机器所判定的语言类。 是类似的非确定性类:对于属于语言的输入至少有一条接受分支,对于不属于语言的输入则没有接受分支,并且所有分支都遵守空间界。 是确定性多项式空间类的并集。
只读约定很重要:若把整条输入带都计入,就已经需要 个单元格,使得对一般输入而言对数界不可能成立。工作带上的计数器仍然可以用 个比特来寻址输入中的位置。在讨论非确定性机器时,这里要求所有分支都停机,下面的可达性算法通过显式限制其步数来实现这一点。
有必要明确说明该约定允许什么。机器可以在输入带上向两个方向自由移动其输入头,读取头下的符号,并按其意愿任意多次地重新扫描输入。它不能在输入带上写入。因此,记住输入的任何信息的唯一方法,是把它写在工作带上,或者让输入头停留在编码该信息的位置。存储一个介于 与 之间的位置需要 个比特,这正是为什么对数大小的工作带恰好足以保存常数个指向输入的指针,或常数个大小为 的多项式的数。这就是对 的工作直觉:对数空间机器是一个配备了固定数量指针和计数器的有限控制器。
通过猜测路径判定可达性
命题 3.1.2
(有向可达性属于 NL)
给定一个有 个顶点的有向图以及指定的顶点 ,在标准的显式图编码下,判定是否存在从 到 的有向路径属于 。
证明
(以计数器猜测简单路径)
若 可达,则一条简单路径至多有 条边:从任意途径中去掉圈即可。将当前顶点和一个计数器各自存储在 个比特中。从 出发,非确定性地选择一个顶点,扫描只读输入以检查所选的边是否存在,并使计数器前进。若到达 则接受;一旦已尝试 条边则拒绝。一条接受分支描述了一条真实的路径,而只要存在路径,简单路径就提供了一个接受的选择序列。所有分支都停机,并且使用对数工作空间。
这一证明的一些细节值得明确说明。情形 已被涵盖,因为机器在走任何边之前先检验当前顶点是否等于 ,所以长度为 的空路径被接受。边的检查使用显式编码,无论是邻接矩阵还是边表,并且需要一个指向输入的指针。输入的长度是 的多项式,因此这样的指针需要 个比特。最后,被猜测的顶点在检查之前写在工作带上,这又多花费一个 比特的寄存器。总的来说,机器保存常数个对数大小的寄存器。
完全性与 Savitch 定理
在对数空间多一归约下,有向可达性是 NL 完全的;可达性完全性配套单元给出证明。Savitch 定理在配套的 Savitch 定理单元中得到证明;它说明对于空间可构造的 ,非确定性空间 包含于确定性空间 。因此 ,并且非确定性多项式空间等于 。这些包含关系并不能确立 ,该问题仍未解决。
完全性将可达性的结果转移到 NL 中每一种语言;可达性完全性配套单元在对数工作空间内构造该归约,并给出对数平方空间算法。配套单元证明了一般 Savitch 定理,也证明了将对数空间归约与可达性算法复合所用的输出带模拟。
有界搜索
例题 3.1.3
(圈并不要求无界搜索)
设图有边 、 和 。机器可能猜测循环 ,但其计数器迫使该分支在经过规定数量的边之后拒绝。另一条分支猜测 并接受。非确定性接受只要求有一条接受分支,而不要求每一个选择都成功。
常见错误
(空间与时间是不同的资源)
对数空间算法并不是由对数数量的步数来定义的。它可以反复扫描输入,重复使用同样的几个工作单元格。反之,显式地存储所有访问过的顶点可能需要线性或更多的空间,尽管这使图搜索变得简单直接。
格局与多项式时间上界
内存很小的机器只可能处于少数几种不同的情形,而这可以被计数。下面的定义使这一想法精确化。
定义 3.1.4
(格局与格局图)
固定一台状态集为 、工作字母表为 的机器 ,以及一个长度为 的输入 。假定输入由端点标记界定,因此输入头有 个可能的位置。设 在 上的每条分支至多使用 个工作单元格。格局是由当前状态、输入头位置、工作头位置( 到 之间的整数)以及 个工作单元格的内容组成的元组。格局图 以这些格局为顶点,当且仅当 的转移规则在应用于 中输入头下的输入符号时,允许 作为 的一步后继时,从 到 有一条边。
的顶点数至多为 ,因为每个分量都可以独立选取。若对某个常数 有 ,则 ,由于 与 是常数,这是 的多项式。因此格局图有多项式多个顶点。这就是对数空间与多项式空间之间的根本差别:当 时,同样的计数给出 ,这是指数级的。
定理 3.1.5
(对数空间包含于多项式时间)
设 是一台带有只读输入带的非确定性机器,使得对于每个长度为 的输入,每条分支都停机,并且对某个常数 至多使用 个工作单元格。则 所判定的语言可由一个运行时间为 的多项式的确定性算法判定。因此 。
证明
(统计格局并搜索图)
固定一个长度为 的输入 ,并记 ;特别地,。格局数 至多为 ,如上所算,它以 的一个多项式为界。一个确定性算法按如下方式进行。首先,枚举所有候选格局。其次,对每一个有序对 ,判定 是否是 的合法一步后继,这需要读取一个输入符号并查阅有限的转移表,因此在最坏情形下耗时为 的多项式。第三,从初始格局出发在 中运行广度优先搜索,当且仅当到达某个接受格局时接受。
关于正确性,从初始格局到某个接受格局、且每一步都遵守转移规则的格局序列,恰好就是 在 上的一条接受分支;反之,每条接受分支都是这样一条路径。总时间至多为 次配对检验(每次为多项式时间),加上耗时 的一次搜索,因此是 的多项式。包含关系 成立,是因为确定性机器就是每一步只有一个选择的非确定性机器,而包含关系 成立,是因为该论证适用于任何所述类型的机器。
证明透视
空间界在多项式时间论证中的位置
这个证明把问题从计算搬到图上,而空间界只在一处用到:统计顶点的个数。把格局写成元组,使个数成为若干独立选择的乘积,而对数的 把因子 变成多项式。算法本身只是对多项式大小的图作普通搜索;它存储整个图及其标记,所以是多项式时间的过程,而不是对数空间的过程。当 时,同一个个数是 ,论证只能给出指数界。正确性方向完全不需要这个界:接受分支恰好对应于从初始格局到某个接受格局的路径。
请注意,这个证明把任意的 计算归约为多项式规模的图上的一个可达性问题,然后在多项式时间内解决该问题。这恰好是另一篇可达性完全性续篇所证明的可达性的 NL 完全性背后的机制。该证明存储了图和搜索标记,因此它是一个多项式时间的过程,而不是对数空间的构造。输出长度本身并不是障碍,因为对数空间归约可以使用只写输出带;对数空间构造按需生成并检验候选的格局对。
更多例题
例题 3.1.6
(为一台具体的机器计数格局)
设一台确定性机器有 个状态和一个二元工作字母表(把空白算作两个符号之一,故 )。在长度为 的输入上,保证它至多使用 个工作单元格;注意 ,所以 。格局数的界为
首先,。接着,。最后,。所以至多约有四千一百万个格局。这个数远大于 ,但仍然是一个多项式规模的集合。相反,如果允许该机器使用 个单元格,仅因子 就会超过 。如果这台确定性机器停机,它的步数少于 ;如果某个格局重复出现,确定性使其永远循环。
例题 3.1.7
(在五顶点图上运行猜测并检验的机器)
设顶点为 ,边为 、、、、,其中 。每个顶点名称需要 个比特,边计数器的取值范围为 ,同样需要 个比特。考虑查询 ,。一条分支猜测 并通过扫描输入检查边 ,然后猜测 ,再猜测 ;经过三条边之后,当前顶点等于 ,该分支接受。另一条不同的分支猜测 :在四条边之后,即 条边,当前顶点是 ,计数器界迫使其拒绝。由于存在一条接受分支,该输入被接受。
现在考虑 ,。从 可达的顶点恰好是 ,因为顶点 没有入边。每条分支要么猜测了一条非边并在边检查时拒绝,要么沿着这个集合内的合法边前进并最终耗尽计数器。没有任何分支到达 ,所以不存在接受分支,该输入被拒绝。在这两次查询中,机器都存储一个当前顶点、一个猜测和一个计数器,这是 个比特,外加输入指针所需的比特。
练习与解答
快速检查
(为什么一个可达的目标总可以通过至多 条边的路径到达?)
解答 · 答案
从任何通往目标的有限途径中,去掉某个重复出现的顶点两次出现之间的片段。重复这一操作,得到没有重复顶点的途径,因此至多有 条边。
快速检查
(为什么 ?)
解答 · 答案
确定性对数空间机器就是在每一步只有一种可能的下一步移动的非确定性机器,所以它满足同样的空间和接受要求。
更多练习与解答
快速检查
(一台确定性机器有 个状态和一个二元工作字母表,在长度为 的输入上至多使用 个工作单元格(注意 )。给出其格局数的界。)
解答 · 答案
界为 。有 ,然后 ,再 。所以至多有 个格局。
快速检查
(设 ,边为 、、、。判定顶点 是否从顶点 可达,并解释猜测并检验的机器会怎样运行。)
解答 · 答案
从 可达的顶点有 ,然后 ,然后 ,然后 ,得到集合 。边 指向 ,提供的是离开 的途径,而不是到达 的途径,并且没有任何边以 为终点。因此 不可达。机器的每条分支从 出发,要么在某次边检查时失败,要么沿着 内的边前进,直到计数器达到 并拒绝。没有分支接受,所以答案为否。
快速检查
(描述一个判定字符串 ()构成的语言的对数空间算法。)
解答 · 答案
首先用有限状态检查扫描输入一次,确认其形如 ,否则拒绝。在第二次扫描中,用一个二进制计数器记录 的个数,该数不超过 ,因此需要 个比特。在第三次扫描中,用第二个计数器记录 的个数。当且仅当两个计数器相等时接受。只用到两个计数器和常数个控制状态,所以工作空间为 。
快速检查
(直接证明:一台对每个输入都停机、并且在长度为 的输入上至多使用 个工作单元格的确定性机器,其运行步数是多项式的。)
解答 · 答案
令 为格局数,由计数界它是多项式。一台停机的确定性机器绝不会两次访问同一个格局:重复的格局会迫使计算永远循环,因为下一个格局是确定的。所以步数小于 ,它是多项式。
快速检查
(在包含途径 的图中,用去圈论证给出一条更短的途径,并说明节省了多少条边。)
解答 · 答案
顶点 出现在位置 和位置 (从 起计)。删除二者之间的部分(顶点 和 以及 的一份拷贝),得到途径 。原途径有 条边,新途径有 条边,所以节省了 条边。新途径中用到的边 来自原途径,因此它在图中存在。