Hartmanis–Stearns 1965：算法复杂度怎样被写成时间可构造的层次

破除误解：层次不是 P 对 NP，加速也不是工程提速#

第一层误解把标题听成「他们已经把所有算法按快慢排好」，或听成已经解决了 $P$ 对 $NP$。原文开篇引用图灵 1936 年的可计算序列，然后说：可计算序列里，有的很容易打印，有的却像带着固有难度。他们要给的不是一张算法名录，而是一套把可计算对象按打印时间分层的数学方案。对象首先是二进制序列：机器从空白带起步，在输出带上依次印出前 $n$ 位，所用操作不超过时间函数 $T(n)$。后来通行的 $\mathrm{DTIME}(t(n))$ 是判定语言的类。第六节才把同一套手续搬到识别问题。把 1965 年收进 1971 年的完全性，会把一次时钟对角化说成一次公式编译。

第二层误解把「更多时间就有严格更多语言」听成无条件句，或听成任意两个可计算函数 $T<U$ 都已经分开两类。对角化机器必须自己知道该跑多久。原文把这份时钟叫做实时可数：存在一台多带机器，在第 $n$ 步印 $1$ 当且仅当 $n$ 落在 $T$ 的值域里。山田 1962 年已证明 $n^k$、$k^n$、$n!$ 都实时可数。没有时钟，模拟器无法在 $U$ 的节拍上准时翻转第 $i$ 台机器的某一位。层次因此不是「时间集合的包含」，而是带时钟的时间函数上的真包含。后来「时间可构造」把同一角色改写成：在输入 $1^n$ 上于 $O(T(n))$ 步内写出 $T(n)$ 的二进制。细节不同，任务相同：对角化需要一只不会自己超时的钟。

第三层误解把加速定理听成「换一盘更快的磁带就按常数倍提速」，或听成已经给出可在车间里缩短墙钟时间的手续。定理说的是类等式 $S_T=S_{kT}$：把相邻两格打成一个符号、把控制里多记住一格邻居，就可以用一步模拟原来的两步。字母表变大，操作计数变小，类不动。正因如此，他们不把「快一倍」当成新的一层。把加速听成工程手册，会把一条存在性模拟收成操作单。

第四层误解把本卷与同年那篇存储器层次焊在一起，或把平方空隙听成已经是紧的层次。磁带复杂度在文中被标成另一条路：迈希尔的线性有界自动机与里奇的可预测可计算函数，用的是带子格子，不是操作步数。刘易斯–斯特恩斯–哈特马尼斯 1965 年的 IEEE 存储器论文是邻居，封面不是这一卷。本页层次的空隙来自通用模拟：固定带数的模拟器要把任意多带机器收成单带，模拟到时刻 $T(N)$ 要付约 $[T(N)]^2$。因此条件写成 $\inf T^2/U=0$，而不是 $T=o(U)$。亨尼与斯特恩斯 1966 年才把多带到两带的模拟改进到 $T\log T$。把 1965 年读成已经没有对数因子的紧层次，会把后年的带压缩提前写进这一卷。布卢姆 1967 年的公理化测度是另一套存在性，不是多带打印时间。

多带机器、时间函数、实时可数时钟，以及平方空隙里的对角化#

装置从一台带有限控制器的多带图灵机开始。控制器挂着固定数目的线性带，两端无界，每条带有一个磁头。每一步根据当前状态与各头下符号，改写符号、让各头独立左移、右移或不动，再改状态。一步操作是时间的基本单位。另有一条只许单向右移的输出带：印出并移走的符号不可撤回。「$n$ 带」不计这条输出带。零带机器就是把输出写在带子上的有限自动机。图灵已证明加带、加符号不扩大可计算函数的集合。他们改用多带，是因为数字计算机在理想化后属于这一类，而快慢对带数敏感。机器从空白带起步。

时间函数 $T$ 是单调可计算函数，并且存在常数 $k$ 使 $T(n)\ge n/k$，以免类落空。序列 $\alpha$ 属于 $S_T$，当且仅当某台多带机器在至多 $T(n)$ 步内印出前 $n$ 位。每个 $S_T$ 递归可枚举：枚举打印机器，各加一只 $T$ 时钟，超时则改印常数零。因而没有任何 $S_T$ 能吞下全部可计算序列。每个可计算序列又落在某个 $S_T$ 里，弱层次已经保证。一般的包含问题却不可判定：把停机编译进「某序列是否属于 $S_T$」，判定手续会解决停机。

加速来自字母表。把相邻两格收成一个符号，并让控制器记住磁头落在双格的哪一半，就可以用一步重放原来的两步。于是 $S_T=S_{kT}$。若 $T/U$ 的下极限为正，则 $S_U\subseteq S_T$。点点最小值仍给出一类。有限多位的改写不改变所属类。这些句子回答的是「哪些计时差别只是换尺子」，不是「怎样把程序写得快一倍」。

模型扰动大多落在平方律里。定理 6：多带上 $T$-可计算的序列，在单带上 $T^2$-可计算。单带把各带对应格子排成块，模拟一步须扫过当前已写区域；已写长度随步数线性增长，总代价平方。因此从 $n$ 带到 $n+1$ 带，最好也只能把时间开到平方根。多头与跳跃指令不改变类：额外的头可用常数倍时间模拟，再被加速吃掉。二维带同样落到平方。稳健性来自「一步只改常数个本地格子」，不来自某一台计算机的总线宽度。本页给出的是类在平方内稳定，不是把磁带折叠写成装配说明书。

层次的强形式是定理 9。设 $U$ 与 $T$ 都实时可数且单调递增，并设 \[ \inf_{n\to\infty}\frac{[T(n)]^2}{U(n)}=0. \] 则存在序列属于 $S_U$ 而不属于 $S_T$。证明是对角化，但必须把模拟开销写进不等式。因为 $T$ 实时可数，可以枚举一批在时间 $2T$ 内运行的二进制输出机器，使每个 $S_T$ 中的序列都出现在名单上。通用模拟器把第 $i$ 台的转移表抄到一条状态带上，工作带按定理 6 的单带方式存放。查表加搬迁，模拟到第 $N$ 位的代价是 $C_i[T(N)]^2$。输出只在 $U$ 的节拍上印一位。因为平方比 $U$ 无穷小，无论模拟第 $i$ 台之前已经耽误多少步，总存在足够大的 $N_i$ 使平方模拟赶在 $U(N_i)$ 之前结束。于是依次翻转名单上各机的某一位，得到一条 $U$-可计算、却与所有 $T$-可计算序列都不同的序列。对角化在这里不是「机器吃自己的描述并永远跑下去」，而是「在 $U$ 的节拍上，平方模拟终将赶上」。本页证明这种翻转存在，不把状态带的标记格式写成攻击步骤。

第六节把同一套话换成识别。识别机多一条单向输入带，第 $n$ 个输出位为 $1$ 当且仅当前 $n$ 个输入字母构成语言中的词，并且必须在 $T(n)$ 步内印出这一位，$T(n)\ge n$。$T$-识别机的集合仍递归可枚举，因而识别问题也可以任意复杂。层次在实时可数函数上同样成立。他们给出一条上下文无关语言：字母表 $\{0,1,s\}$，一个词属于该语言，当且仅当最后一个 $s$ 之后的 $0$-$1$ 串，是此前某一段的镜像。语言是上下文无关的，却不能被实时识别：在额外 $i$ 步内，磁头附近能区分的历史配置随 $i$ 指数增长，而长度为 $i-1$ 的 $0$-$1$ 串的子集有双指数多个。实时因此不是「上下文无关」的自动礼物。这是文中第一则显式不可能性。

第五节把序列读成实数的二进制展开。有理数落入 $S_n$，代数数落入 $S_{n^2}$，$n!$ 的实时计数器又给出 $S_n$ 里的刘维尔超越数。他们写下开放问题：有没有无理代数数也在 $S_n$ 里。本页记录这个问题被提出，不把后来的进制展开研究写成已经收进 1965 年。

它证明了什么，没有覆盖什么#

它证明了：可计算序列按多带打印时间分成递归可枚举的类 $S_T$，没有任何一类等于全部可计算序列；线性加速使类对正常数倍的时间重标度不变；多带与单带之间至多相差一次平方；在实时可数的时钟上，若较大时间函数比平方模拟开销增长得更快，则严格更多的序列可被打印。识别问题上，存在不能实时识别的上下文无关语言。包含问题不可判定。用后来的语言，核心就是：时间可构造的界上，更多时间给出严格更多的可计算对象。总览页那句「由此可知 $P$ 真包含于 $\mathrm{EXPTIME}$」是后年把多项式档与指数档放进同一条层次之后的推论，钉子的金属成分以 1965 年的 $T^2/U$ 条件为准。

它没有证明 $P\neq NP$，也没有给出完全性问题。完全性是归约闭包：每个短证书语言都可被翻译到 SAT。层次是对角化：在更松的时钟上构造一个故意与所有更紧机器不同的对象。箭头方向相反。库克问的是多项式时钟内的存在性量词；卡普问的是哪些组合判定与可满足性同生共死；本页问的是确定性打印的时间标度本身能否被压扁。把 SAT 听成 1965 年的对角序列，会把一次补位收成一次窗口编码。它也没有证明空间上的平行句子。Savitch 1970 的平方出现在工作带复用上，本页的平方出现在通用模拟的带压缩上。两个平方不是同一个账本。存储器层次要读那篇 IEEE 论文，不要从《汇刊》第 117 卷里「看出来」。

它没有给出紧层次。原文第七节把改进定理 9 写成公开问题：$T/U\to 0$ 与 $T^2/U\to 0$ 之间仍有空隙。亨尼–斯特恩斯 1966 年的带归约把模拟开销收到对数。把教材里「$t_1\log t_1=o(t_2)$ 则 $\mathrm{DTIME}(t_1)\subsetneq\mathrm{DTIME}(t_2)$」读回这一卷，会把 1966 年的对数因子写成 1965 年的定理。它也没有采用布卢姆的公理语言。

它没有覆盖非确定性时间。机器每一步的转移是唯一的。本页的 $S_T$ 是序列类，不是语言类；识别版要求单向输入且每位都输出是否成词，与后来「读完输入后停在接受态」的判定机仍有一句之差。把 $S_n$ 直接写成正则语言，或把 $S_{n^k}$ 写成 $P$，会把打印前 $n$ 位的时间函数偷换成「输入长度 $n$ 的判定时间」。稳健性来自时钟可构造与模拟开销可估计，不来自后来的求解器。概念证据到此为止。实时可数回答的是「对角化凭什么知道该在哪一步翻转」；平方空隙回答的是「通用模拟在 1965 年要付多少时间账」。两句都不是操作单。

跨域连接#

• 计算复杂性：总览页把时间层次写成地图上已钉死的一格：$P$ 真在 $\mathrm{EXPTIME}$ 之下，这不是猜想。钉子的形状是带时钟的对角化，不是后来的完全性问题清单。把总览里那句「更多时间给出更多语言」提前读成本页，会漏掉实时可数与平方空隙。地图可以后写；本页只提供 1965 年那一次把可计算世界切成时间层的手续。
• 可计算性：图灵把序列分成可计算与不可计算；本页假定序列可计算，再按打印时间分层。停机问题的对角化没有平方时钟，机器可以把自己的描述吃下去并一直跑。这里的对角化必须在 $U(N_i)$ 步内结束，因此需要一只实时可数的钟。可判定与在时间 $T$ 内可打印是两层边界。把层次听成又一次停机，会把资源问题收成存在问题。包含问题不可判定，说明分类方案本身仍坐在停机的不可判定性上。
• Cook 1971：库克把非确定性多项式时间的接受计算编译成布尔公式，问的是完全性。本页六年前把确定性打印时间写成可分层的标度。完全性说「若汇点容易则源点容易」；层次说「松一档时钟就出现一个新对象」。库克已指出停机那套对角化套不上多项式量词；本页表明对角化在确定性时间标度上是够用的。同一套自指技术，一旦中间隔着一个存在性量词，就会从层次定理变成障碍。
• Savitch 1970：萨维奇的平方把非确定性空间压进确定性磁带；本页的平方把多带时间压进单带模拟。资源不同。萨维奇问的是格局图上的可达性，寄存器复用给出 $L^2$；本页问的是通用机器模拟任意带数时扫过的格子，区域长度给出 $T^2$。空间后来被二次模拟压回同一多项式档，$\mathrm{PSPACE}=\mathrm{NPSPACE}$；时间没有平行句子。把两处平方焊成一句「1960 年代的平方定理」，会把磁带复用与带压缩收成同一个因子。同年那篇存储器层次论文才是空间侧的兄弟，仍旧不是这一卷。
• 自动机与形式语言：零带机器就是有限自动机，有理数的最终周期落入 $S_n$。他们引用乔姆斯基 1959 年的文法论文，并构造一条不能实时识别的上下文无关语言。实时识别比「属于上下文无关」更严。线性有界自动机与磁带分类被点名为另一条路，留给迈希尔、里奇，也留给同年那篇存储器论文。本页不把镜像语言改写成扫描器实现指南。
• 弗洛伊德 1967：两年后弗洛伊德给程序流程图的边贴上断言，问的是命令的意义能否与处理器脱钩。本页问的是同一批多带机器打印序列有多快。一个给意义，一个给资源。弗洛伊德的归纳断言不计量步数；本页的时间函数不验证部分正确性。

参考文献#

• J. Hartmanis & R. E. Stearns, "On the Computational Complexity of Algorithms", Transactions of the American Mathematical Society 117, 1965, pp. 285–306. DOI: 10.2307/1994208. —— 本文对象：多带时间类 $S_T$、加速、平方模拟，以及实时可数函数上的时间层次。
• J. Hartmanis & R. E. Stearns, "Computational Complexity of Recursive Sequences", Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, 1964, pp. 82–90. —— 论文所引的预先宣布。
• H. Yamada, "Real-Time Computation and Recursive Functions Not Real-Time Computable", IRE Transactions on Electronic Computers EC-11(6), 1962, pp. 753–760. DOI: 10.1109/TEC.1962.5219459. —— 实时可数时间函数，层次定理的时钟。
• A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society (2) 42, 1937, pp. 230–265. —— 论文开篇所划分的可计算与不可计算序列。
• M. Davis, Computability and Unsolvability, McGraw-Hill, New York, 1958. —— 论文所引的图灵机与停机问题传统。
• M. O. Rabin, "Real-Time Computation", Israel Journal of Mathematics 1, 1963, pp. 203–211. DOI: 10.1007/BF02759719. —— 论文所引的实时计算邻居。
• A. N. Chomsky, "On Certain Formal Properties of Grammars", Information and Control 2(2), 1959, pp. 137–167. DOI: 10.1016/S0019-9958(59)90362-6. —— 论文识别节所引的文法背景。
• R. W. Ritchie, "Classes of Predictably Computable Functions", Transactions of the American Mathematical Society 106, 1963, pp. 139–173. DOI: 10.1090/S0002-9947-1963-0158822-2. —— 论文点明的磁带分类邻居，用以标明时间与带子不是同一测度。
• J. Hartmanis, P. M. Lewis II & R. E. Stearns, "Hierarchies of Memory Limited Computations", 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 179–190. DOI: 10.1109/FOCS.1965.11. —— 同年存储器层次，用以标明空间论文不是本卷封面。
• F. C. Hennie & R. E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", Journal of the ACM 13(4), 1966, pp. 533–546. DOI: 10.1145/321356.321362. —— 后年把平方模拟收到对数，用以标明紧层次不是 1965 年的定理。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 用以标明时间完全性不是 1965 年的对象。
• Walter J. Savitch, "Relationships Between Nondeterministic and Deterministic Tape Complexities", Journal of Computer and System Sciences 4(2), 1970, pp. 177–192. DOI: 10.1016/S0022-0000(70)80006-X. —— 用以标明磁带平方不是本页的平方。

延伸阅读#

• 与 计算复杂性 对读：先看时间层次在地图上已钉死的那一格，再看本页的时钟与平方空隙。
• 与 可计算性 对读：停机对角化没有时钟；本页的对角化必须在 $U$ 的节拍上结束。
• 与 Cook 1971 对读：确定性时间标度可分层，隔着存在性量词则变成完全性。
• 与 Savitch 1970 对读：空间平方与时间平方是两本账。
• 与 卡普一九七二年论文 对读：多一完全性与无条件时间层次不是同一类箭头。
• 与 自动机与形式语言 对读：上下文无关不蕴含实时可识别。
• 与 弗洛伊德 1967 对读：意义合同与时间分层是同一年代里的两条路线。