跳转到内容

线性加速定理

维基百科,自由的百科全书

计算复杂性理论中,图灵机的线性加速定理是指:给定任意实数 c > 0 ,如果有任意图灵机在 f(n) 时间内可以解决一个问题 L 则一定存在另一个图灵机可以在 cf(n) + n + 2 的时间内解决这个问题 L[1]

简要证明

[编辑]

这里提供一个对于 c = 1/2 时的简要的证明思路。假设一个包含有 k 条带和 s 个状态的图灵机 M 可以在 f(n) 的时间内解决这个问题,构造一个新的图灵机 M' 包含 k3 条带,每一个符号表示一个 M 中连续的三个符号的一个区块,即 M' 的带上的符号是 M 上的符号的压缩表示—— M' 的第 i 格上的符号表示 M 的第 2i-1 格、第 2i 格和第 2i+1 格的一个区块上的符号(注意:这些区块之间是交叠的)。在一个计算步骤中,M' 模拟 M 的计算步骤直到 M 的读写头离开 M' 当前读写头所表示的对应区块到左侧或右侧的下一格(这一模拟可以在一步中完成,因为 M 在不离开 M' 中对应区块或重复一个状态的情况下最多有 3sk3 种状态)。在这一模拟过程中, M 有可能接受(解决此问题),对应的 M' 也会接受(解决此问题);或者 M 会一直循环下去,对应的 M' 会什么也不做(或也对应的一直循环下去)。

最后一点需要注意的地方是:由于区块可以交叠,因此这些区块可能会在交叠出包含不连续的字符。在这种情况下,最接近当前读写头位置的区块才是正确的。当发生从一个区块到另一个区块的转换时,图灵机的状态被用来暂时记录开始区块的那些交叠的符号,直到其可以被复制到目的区块的对应位置。

这一构造需要 M' 的每一步计算要对应 M 的至少两步计算。因此 M' 在最初的花费线性步骤的将输入带转换为压缩表示的步骤之后,最多还需要不会超过 f(n)/2 步。

这一证明可以被很容易的推广到所有的 c > 0 的情况,通过让每个区块使用更多相邻的符号来实现。一种叫做“带压缩定理”的相似技术可以用来在图灵机所需的空间上去掉常因数。

引用

[编辑]
  1. ^ 赫里斯托斯·帕帕季米特里乌. 2.4. Linear speedup. Computational Complexity. Addison Wesley. 1994.