为什么计算模型之间需要证明
描述验证者时,用一条纸带存输入、一条存证书、另一条做草稿很方便;构造计算表时,却可能要求只有一条纸带和一个读写头。两种描述之间必须有数学上的桥梁:模拟器既要保留答案,也要把额外耗时控制在所声称的资源范围内。
本节为固定有限条普通图灵(Turing)机纸带建立这座桥梁。我们写出表示方式、证明不变量,并计算实际扫描耗时。这个初等构造证明多项式时间的稳健性,但不证明确定性时间层级章节所使用的更精细的通用模拟界。
两种模型
定义 4.2.1
(多带图灵机)
固定正整数 和有限纸带字母表 ,其中包含输入符号 与空白符。 带图灵机有一个有限控制器,以及 条以整数为坐标的双向无限纸带。一次转移读取各头下的 个符号,改变状态,在每条带上写一个符号,并把各头移动 中的一个距离。、字母表和转移表属于固定机器,不是输入的一部分。
对于 ,第一条带在坐标 存放 ,其余位置为空白;其他带完全空白。所有头从坐标零出发, 时也一样。接受和拒绝状态都是停机状态。时间以转移次数计, 限制每个长度为 的输入上的耗时。
模拟器只有一条双向无限纸带和一个头,可以使用比 更大的固定有限字母表。字母表大小只依赖被模拟机器。本节把输入放在计入使用范围的纸带上,只讨论时间;它不证明带有独立免费输入带的对数工作空间模拟。
把虚拟纸带存成多轨记录
定义 4.2.2
(虚拟纸带的多轨表示)
每个被表示的坐标 对应一个物理格,其记录含有 个虚拟纸带符号,以及每轨各一个旧头标记和新头标记。区间两端以分隔符界定。被模拟的控制状态保存在模拟器的有限控制器中。
每次虚拟转移开始时,保持以下不变量:
- 每轨恰有一个旧标记,位于该虚拟头的当前位置;所有新标记均为空。
- 区间内记录等于当前虚拟纸带内容,区间外所有虚拟格均为空白。
- 各虚拟头均在区间内,有限控制器保存正确的被模拟状态。
不含分隔符时, 种记录就足够。因此一条记录可作为固定字母表中的一个符号。这里同时保存 个符号是合法的,因为 固定;我们没有假设可用单位时间处理随输入增长的纸带数。
初始化扫描输入,把每个输入符号改写成记录,其他轨填空白。空输入则在坐标零建立空白记录。在各轨的坐标零放旧标记,两端各补一个空白记录,再在外侧放分隔符,耗时 。记 ,初始区间可取 ,共有 条记录。
例题 4.2.3
(两个虚拟头可以位于同一个物理格)
设 ,第一带存 ,第二带为空。在坐标零,记录的符号对为 ,两个旧标记都置位。它们是同一记录中的不同位,表示两个虚拟头。唯一的物理头一次读出整条记录。之后虚拟头可以分开,物理头便在不同时刻访问它们所在的记录。
用固定次数的扫描完成一次转移
先在区间两端各增加一条空白记录,并把两个分隔符各向外移一格,原端点记录不变。寻找另一端所需的遍历也计入扫描耗时;固定次数的遍历足够完成扩展。因此,即使旧头在端点,下一次转移的目标格也已被表示。
接着从左向右扫描。第 轨唯一的旧标记给出其读取符号 。把 存在有限控制器中,由它与当前状态确定转移:下一状态、各轨写入符号及移动方向。这些数据对固定机器都只有常数大小。
向回扫描并执行更新。遇到第 轨的旧标记时,在该轨写规定符号并清除旧标记,再按方向在本格或相邻格放第 轨的新标记。物理头可短暂移动到相邻格、修改相应字段,然后返回,继续主扫描;经过其他字段时保持其值。若同一格有多轨旧标记,就按固定轨次序处理。
更新只识别旧标记。新目标格可能已扫描,也可能尚未扫描,这不会改变本次要处理的旧标记集合。访问邻格时,不递归调用更新过程;有限控制器记住自己正在完成局部往返,返回后才恢复主扫描。旧标记总共只有 个,故这样的往返至多 次。
最后再扫描整个区间,把所有新标记改为旧标记,存入下一状态,并回到规定边界准备下一轮。完成 轮后,区间可为 ,含 条记录。无论虚拟头如何移动,每轮只增加两条记录。
定理 4.2.4
(模拟不变量的保持)
每轮结束后,记录与所存状态恰好编码原机器执行一次转移后的格局。因此模拟器与原计算的接受、拒绝结果一致。
证明
(对轮数作归纳)
初始化满足不变量。假设某轮开始前成立,扩展区间只添空白,与原区间外的虚拟内容一致。收集扫描读到准确的旧符号元组,所以选中原机器的同一转移。对每轨,更新只改动旧头所读的符号,并在指定目标恰好放一个新标记,其他符号保持原值。新标记不触发更新,故不会把一次转移执行两次。清理后,各轨又恰有一个旧标记,新字段全空,所存下一状态也正确。对轮数归纳即得结论。遇到被模拟停机状态就结束;初始状态已停机的情形,可在初始化后识别。
证明透视
旧标记与新标记如何支撑归纳
除了更新规则之外,归纳还用到三项事实。收集扫描在任何写入之前结束,所以转移只由旧格局选出;这就是“选中原机器的同一转移”的意思。写入只产生新标记,而更新扫描只对旧标记作出反应,所以无论目标格相对于扫描处在哪一侧,都不会有任何东西被执行两次。清理只是重新命名角色,而不是搬动数据,从而恢复不变量。两端各添加的缓冲记录,使不变量的第 3 条在头向外移动一步后仍然成立; 固定,则使被扫描符号的元组可以存放在有限控制器之中。若取消新旧标记的区分,下面例子中的失败就会出现。
下面的例子说明,把两组标记字段分开,排除了什么问题。
反例模式
只有一种头标记为何危险
设更新从左向右,虚拟规则使头右移。如果清除坐标零的标记后,立即在坐标一放普通头标记,那么下一次扫描到坐标一时,可能再次应用规则。一次虚拟转移便使头移动两次,甚至一直重复到边界。把扫描方向反过来也不能普遍解决,因为机器也能左移。分开的旧、新字段用同一个不变量处理两个方向。
计算物理步骤,而不是虚拟指令
定理 4.2.5
(平方量级的模拟开销)
对每台固定的确定性 带机器,若其耗时不超过 ,则上述确定性单带模拟器耗时
若 ,此界为 。隐含常数可以依赖固定机器,包括 和其字母表。
证明
(累计所有轮次的耗时)
第 轮开始前已模拟 步。计入新缓冲格,区间有 条记录。每轮扫描次数固定,局部常数距离往返至多 次,每个记录的处理也是常数时间,所以该轮耗时 。原计算若实际执行 步,初始化及各轮总耗时至多
从而得到定理中的界。 时求和为空,但初始化仍需 。模拟器无须知道 或计算时钟:它反复模拟,直到原机器停机;时间界用于外部分析。
例题 4.2.6
(多项式界仍然是多项式)
一个固定三带验证者在总编码长度为 的实例与证书上,最多执行 次转移。单带模拟耗时 。之后的单带计算表构造可采用这个更大的多项式界,不能仍把原先的三次截止时间原封不动地套在模拟器上。
例题 4.2.7
(立即停机也要支付本构造的初始化成本)
一台立即拒绝所有输入的机器有 。这里的模拟器先扫描、编码输入,再报告拒绝,需要 ,符合一般界。若直接套 就会得到无意义的零界,因为其前提 不成立。专门优化当然可以省去扫描,但那不是已给出的构造。
非确定性与多项式类
对非确定性机器,时间界必须限制每条分支。收集扫描符号后,模拟器非确定地选择原机器的一条可用转移;其余扫描、记录和清理都确定执行。没有可用转移的死端拒绝,除非它已经是接受停机。对每个选择序列,上述不变量分别成立,所以模拟器有接受分支,当且仅当原机器有接受分支;所有分支都满足同一开销界。无需猜测纸带内容或头位置。
推论 4.2.8
(固定纸带数给出相同的 P 与 NP)
把一条纸带改为任意固定有限条纸带,不改变确定性多项式时间可判定的语言集合。在所有分支均有多项式时钟的非确定性模型中,也不改变相应语言集合。
证明
(化为单带情形)
单带机可直接当作忽略其余纸带的多带机。反向则把任意多项式界扩大成仍为多项式且满足 的界,模拟只会再得到另一个多项式。逐分支论证给出非确定性结论。同理,证书编码长度为多项式的确定性多带验证者,可改成单带多项式验证者,且接受的证书集合不变;时间始终按实际编码长度计算。
常见错误
常见错误
(多项式稳健性不等于保留指数)
本结果保留多项式时间归属,不保留精确指数。它不证明两种模型的线性或平方时间类相同,不给出时间层级论证所需的 通用模拟,也不保留对数空间。
常见错误
(纸带数必须保持固定)
若 随输入长度增长,记录不再来自同一个固定有限字母表,必须另建明确计费的模型。
练习
快速检查
(若 且 ,不含分隔符时有多少种符号与标记记录?为何可以使用它们?)
解答 · 答案
符号对有 种,四个标记位有 种,共 种。它只依赖固定机器,因此可放进一个固定有限字母表,不随输入增长。
快速检查
(长度为四的输入模拟七步后,上述表示可使用什么区间,共多少记录?)
解答 · 答案
,区间为 ,共有 条记录,与 一致。
快速检查
(某头左移到主更新扫描已经过的记录,为何仍能正确表示其新位置?)
解答 · 答案
局部往返在那里设置新标记后返回。主更新扫描不必重访;后面的清理扫描经过全区间,把新标记改成旧标记。该轨的格中符号仅在它原本就是旧头所读的格时改变。
快速检查
(为何必须在任何虚拟写入前先收集全部读取符号?)
解答 · 答案
原机器的一次转移同时读旧符号元组。若用部分已更新信息选择转移,就可能读到不同元组并选错规则。先收集使读旧格局与写新格局分离。
快速检查
(固定多带算法耗时 ,本构造给出什么上界?是否也证明对应下界?)
解答 · 答案
先把界扩大到至少 ,再平方,对 得 ; 另取有限约定。这只是某个模拟器的上界,既不是原语言的时间下界,也不证明模拟最优。
快速检查
(为何只限制接受分支的长度,不足以推出这里的非确定性耗时结论?)
解答 · 答案
拒绝分支可能任意长,甚至不停机,模拟器沿着该分支也就没有多项式时间保证。标准非确定性多项式时间模型对每条分支施加时钟;存在接受分支是另一个条件。
快速检查
(验证者读入长度 的编码对,其中 为多项式,耗时 。证明单带模拟对 仍为多项式。)
解答 · 答案
对 为多项式。扩大原时间界使其支配 ,模拟耗时为 ,故对 仍为多项式;不变量保证接受证书集合不变。
快速检查
(本证明能否替代精细时间层级定理中的对数开销通用模拟引理?指出缺少什么。)
解答 · 答案
不能。这里对每台固定机器,在时间支配输入长度时给出平方界。精细层级证明可能需要只增加对数因子的通用模拟器,还须控制机器描述的处理成本;这两个更强结论都未在此建立。