动机
上一节的确定性可达性算法在每层递归中只保存两个端点及一个候选中点。对于有 个顶点的图,它使用 空间。一台使用 空间的机器大约有 个格局。代入 ,便得到 的模拟空间这一猜想。
但代入公式还不是证明:如果先把整个格局图写出来,可能已经用掉指数空间。我们必须在不存储图的情况下生成顶点名称、枚举中点和检查邻接关系,还要说明模拟器如何得知空间界限、递归为何停机,以及为何不会漏掉接受计算。这些细节正是一般定理的核心。
定义与机器约定
所有对数以 为底。输入长度为 ,允许 。机器有一条带端点标记的双向只读输入带,以及固定有限条工作带;状态集、字母表和工作带数目都不随 改变。空间只计算访问过的工作带单元,不计算输入带。改用单条工作带只影响下文界限的常数因子,所以用单向无限工作带描述格局即可。
定义 3.2.1
(空间类与可计算的空间界限)
与 分别由能以 工作空间判定的语言组成,前者使用确定性机器,后者使用非确定性机器。非确定性判定器的每条分支都停机,且恰在至少一条分支接受时接受。这里采用一个方便的空间可构造性假设: 取整数值,,并且有确定性过程在输入 上,以 空间算出 的二进制表示,且划定含 个单元的工作区域。
这一明确假设足以证明标准的空间可构造版本。常见界限如 、它的平方及 的正整数次幂均满足它。模拟器不必真的保存 :只需保存虚拟读头位置,判断它是否位于 ,便能模拟一元输入。额外的 位已包括在 预算内。
固定一台判定某个 语言的机器 。选取足够大的整数常数 ,使每条分支最多使用 个工作单元。一个格局记录状态、输入读头位置、工作读写头位置及全部 个工作符号,包括未使用的空白。给定 后,各字段的长度固定。若状态集为 、工作字母表为 ,格局元组数至多为
除固定数目的分隔位外,每个元组可用
位编码。各项都为 ,特别是输入读头字段由 控制,而工作读写头字段满足 。
不必存储的图
选定公共标签长度 ,足以编码全部格局和一个额外目标 。例如,在每个元组前加 ,用一个以 开头的标签表示 ,其余不能解码的标签均视为无效。把全部 个标签视为顶点,无效标签是孤立点。若 的一步合法转移在 单元窗口内把 变为 ,就有边 ;若 是接受格局,就加边 。目标 没有出边。真实初始格局的标签记为 。
命题 3.2.2
(隐式格局图)
该图的边谓词可在 工作空间内判定。并且, 接受 ,当且仅当从 可达 。
证明
(证明)
给定两个标签,先检查它们的字段是否表示格局或指定目标。对于格局间的边,查阅固定转移表,扫描真实输入以读取第一个标签所指定的输入符号,检查状态变化、允许的读写头移动和所写符号,并逐项确认其余工作符号未变。固定数目的标签和扫描计数器共需 空间。检查接受格局到目标的边更简单。其余情况一律拒绝,包括离开工作窗口的移动。
接受计算沿合法格局走到接受格局,再走一步便到达 。反过来,到达 的通路最后一步必来自接受格局。从真实初始格局出发,沿边归纳可知前面每一步都属于 的合法计算。无效标签没有相邻边,不能制造虚假的接受通路。真实空间界限又保证删除窗口外转移不会删除任何从 出发的计算。
我们枚举的是所有标签,而不是仅仅枚举可达格局。后者本身就需要解决可达性,若把它作为建图的前提,论证便会循环。语法有效性容易检查;从初始格局能否到达,则交给下面的搜索。
定理与证明
定理 3.2.3
(Savitch 定理)
在上述空间可构造性及下界假设下,
模拟器是确定性的,并在每个输入上停机。
证明
(通过有界中点搜索证明)
对于标签 和整数 ,用 表示存在从 到 、边数至多为 的通路。层次为零时,恰在 或存在边 时返回真。层次为正时,依次枚举全部 位标签 ;若某个 使 与 都为真,就返回真。若全部候选都失败,则返回假。
对 归纳证明正确性。基础情况恰好包含零边及一边通路。两条各至多有 条边的通路拼接后,边数至多为 。反过来,对于长度 的通路,取经过 条边后的顶点为中点,两段长度为 与 ;当 时,两者均不超过 。空通路可取 。由归纳假设,递推的两个方向都成立。
在有 个顶点的图中,从起点可达的顶点必有一条至多含 条边的简单路径:反复删除两次出现同一顶点之间的部分即可。因此, 为真当且仅当 接受。即使图中有环,该路径界限仍成立。
现在计算同时占用的存储。一个递归栈帧保留 、当前中点 、层次 和固定数目的控制标志。三个标签占 位,层次占 位,所以每帧为 。枚举计数器仅保存一个 位串;处理全一串之后设置结束标志,不需要把全部标签存下来。层次从 降到零,至多有 个活动栈帧。
同一中点的两次递归调用按顺序执行。第一次返回后先释放其临时栈帧,只保留一个布尔(Boolean)结果,再决定是否执行第二次。因此栈空间为 。计算空间界限和边测试的辅助区域另需 空间,总计 。每次调用只枚举有限个候选,且子调用层次严格下降,所以对层次归纳可知每次调用都停机;计算空间界限的过程亦按假设停机。
证明透视
Savitch 证明各部分各自负责什么
这个证明有三个容易混淆的成分。递推式只是关于途径的陈述:把长度至多为 的途径在中间顶点处分开,两半的长度都至多为 ,而 的情形处理比界更短的途径。起始层次 来自简单路径论证,因为图有 个标签;图中的环只在这里才有影响。空间界来自另一处:两个递归调用一先一后地运行,第一个调用的存储在第二个开始之前就已释放,而栈至多容纳 个各占 位的帧。若保留已完成调用的结果,或让两个调用并排运行, 的界就会丧失。机器 只通过边谓词进入证明,而边谓词可在 空间内计算。
递归会重复求解相同问题。调用树的分支数至多为 ,深度至多为 ,故调用总数为 。输入扫描和标签比较增加的 的多项式因子可吸收到 中。计算空间界限的确定性停机过程只有 个格局,其时间也被吸收。这是此模拟的时间上界,并非该语言的时间下界。把所有结果都缓存下来,会改变空间分析。
概念视角结构
栈是调用树上的一条路径
把递归看成深度为 的子问题树:询问 的结点逐一尝试各个中点 ,每次尝试有两个位于层级 的子结点。确定性的运行以深度优先方式遍历结点。任何时刻,只有从根到当前结点的一条路径上的结点是活动的,所以内存是路径长度 乘以帧大小 ,不论整棵树有多少结点。
例题详解
例题 3.2.4
(从对数空间到对数平方空间)
设 在固定字母表上最多使用 个工作单元。格局数为 的多项式,标签宽度为 ,活动递归层数也是 。两者相乘得到确定性空间 ,而非 。因此,单靠 Savitch 定理不能证明 。
例题 3.2.5
(多项式空间仍然是多项式)
若非确定性判定器使用 空间,模拟器使用 空间。次数变了,但仍为多项式。定义 ,并用确定性机器类似定义 。Savitch 定理给出前者包含于后者;把确定性机器看作每步只有一个选择的非确定性机器,又得到反向包含。因此 。这没有证明三次空间等于六次空间:类相等依赖于对所有多项式界限取并集。
例题 3.2.6
(中点不一定把长度平分为相同整数)
设仅有边 、、。查询 允许四条边,但实际见证只有三条。取 ,两段长度分别为一和二,所以两个层次一的调用都成功。若错误地要求每段恰有两条边,则会拒绝,因为这里不存在四边通路。“至多”及基础情况中的 允许较短路径,不必向图中添加自环。
按需模拟归约的输出带
上一节的对数空间归约可能输出一个多项式大小的图。把归约与小空间图算法复合时,同样不能先保存全部输出。
命题 3.2.7
(按需输出模拟)
设确定性对数空间转换器 停机,输出长度有多项式上界,并使用先前内容不影响转移的只写输出带。若语言 的判定器在长度为 的输入上使用 空间,则 可用 空间判定。
证明
(证明)
先运行 ,只计数输出符号而不存储它们,以求出 。输出长度有多项式上界,所以计数器只需 位。模拟 的判定器,保存其工作带及虚拟输入读头的位置 。每当它请求位置 的符号,就从头重跑 ,数到第 个输出符号并返回它; 以外的端点位置返回相应标记。
重跑转换器需要 辅助空间,暂停中的判定器保留 空间。二者相加仍满足界限。每次重跑及被模拟的判定器都停机,而它读取的恰是 ,故模拟正确。
例如,若输出是邻接矩阵,查询某一项时便重跑归约,直至它输出该项。重新计算很长的前缀耗时,却只需少量可重用内存。此命题与之前的 NL 完全性归约及确定性可达性证明结合,也能推出 ,不必引用一般定理。
常见错误与证明界限
常见错误
(一般可达性图中的环)
图中若有边 、 及 ,接受通路可以先绕环多次才到达 。后来的选择可以离开环,所以重复顶点并不迫使每种后续选择永远循环。然而,不断选择绕环会产生无限通路。因此,该例不能是每条分支都停机的判定器的格局图的可达部分。删除环说明即使在一般图中也存在较短接受见证,却不限制一般图中每条通路的长度。我们的搜索证明也适用于这个更广的情形。
下界 用于支付输入读头字段的空间。没有它,显示出的编码大小只是 ,本证明便不能给出 。也不能随意选择一个不可计算的空间预算,却假定模拟器知道如何划定它;空间可构造性正是提供这一过程。这是在说明本证明的适用范围,并非断言所有表述都必须有相同假设。
反例模式
以“每个中点”代替“某个中点”
一个诱人的变体,是把“某个中点可行”改为“每个中点都可行”,期望借此同时模拟全称选择。取顶点 、 和一个孤立顶点 ,仅有一条边 。此时 应当成立,因为 经一条边即可到达。取中点 时, 与 都成立, 亦然。但取 时, 不成立,因为 且没有边 。于是全称规则回答为假,尽管 可达。递推式只有在存在性选择之下才正确;兼有两种选择的交替式机器须另作分析。
练习
快速检查
(为何可以把从 不可达的格局标签留在图中?为何随意添加从可达格局出发的边会有危险?)
解答 · 答案
从可达格局出发的每条边都经过转移检查,所以沿路径归纳始终保持合法可达性;别处的有效格局不会制造假阳性。但任意添加边可能把可达区域接到原本不可达的格局,再通向接受格局,破坏这一不变量。例如,直接加一条从初始格局到接受格局的边,就可能把拒绝变为接受。
快速检查
(一台机器有 个状态、包括空白符号的二元工作字母表,输入长度为 ,工作窗口含 个单元。计算格局数上界,并给出加上目标后足够的递归层次。)
解答 · 答案
上界为 。加上目标后至多有 个顶点,所以简单路径至多有 条边,层次 已足够。证明中的显式编码使用 位和层次 ,这是较大但同样足够的选择。
快速检查
(说明为什么保留所有已经完成的子问题的实现可能失去 空间界限。)
解答 · 答案
单一层次可有 对端点,因此为所有端点对保存答案的表可能需要指数多个条目。Savitch 的栈只保留 个活动帧,刻意重算已经完成的问题。这是某种缓存实现可能付出的代价,不是对所有算法的下界。
快速检查
(将定理用于 ,写出确定性空间界限及此模拟的时间上界。)
解答 · 答案
空间为 。由 得到搜索时间上界 ,其中已吸收输入扫描因子。
快速检查
( 是否推出 或 ?明确解释证明实际上提供了什么。)
解答 · 答案
两个结论都不由本论证推出。多项式的平方仍属于所有多项式空间界限的并集;对数的平方则给出一个更大的已陈述界限。该构造也没有提供非确定性的多项式时间模拟。
快速检查
(若归约输出长度至多为 ,虚拟输入读头需要多少空间?为何重跑归约会保持该位置的符号不变?)
解答 · 答案
位置至多为 加端点标记,因此需 位。确定性转换器在相同固定输入上从头运行,总会输出相同序列;数到保存的位置就得到同一符号,不必保留以前的输出。
关键计算现在已明确:每个格局占 位,搜索有 个活动层次,顺序子调用重用临时空间。非确定性空间的补封闭及多项式空间完全问题等后续主题,还需要新的论证。