math - 如果非确定性图灵机在 f(n) 空间中运行，那么为什么它在 2^O(f(n)) 时间中运行？

Question

假设 f(n) >= n。

如果可能的话，我想要一个关于图灵机的证明。我理解为什么使用在二进制上运行的机器的原因，因为每个“磁带单元”都有一点 0 或 1，但在图灵机中，磁带单元可以包含任意数量的符号。我很难理解为什么基数是“2”而不是像“b”这样的东西，其中“b”是图灵机磁带的符号类型数。

Answer 1

这里重要的细节是运行时间是 2 ^O(n)而不是O(2 ⁿ )。换句话说，运行时间是“2 次方的 O(n)”，而不是“2 ⁿ量级的东西”。这是一个微妙的区别，所以让我们稍微剖析一下。

让我们考虑函数 4 ⁿ。这个函数不是 O(2 ⁿ )，因为从长远来看 4 ⁿ会超过 2 ⁿ。但是，请注意 4 ⁿ = 2 ²ⁿ，并且由于 2n = O(n) 我们可以说 4 ⁿ = 2 ^O(n)。

类似地，对任何底 b 取 b ⁿ。如果 b > 2，则 b ⁿ不是 O(2 ⁿ )。但是，我们确实有

b ⁿ = 2 ^{(lg b) n} = 2 ^O(n)

因为 (lg b) n = O(n)，因为 (lg b) 只是一个常数因子。

^{O(2 n} ) 与 2 ^O(n)不同，这绝对有点奇怪。第一次看到在指数中使用大 O 表示法的想法有点奇怪（例如，n ^O(1)的意思是“由多项式限制的东西”），但通过练习你会习惯的。