时间复杂性

定理 设函数 $t(n)\ge n$, 则每个 $t(n)$ 时间多带 TM 和某个 $O(t^2(n))$ 时间单带 TM 等价.

对 NTM, 其运行时间 $f(n)$ 是在所有长度为 $n$ 的输入上, 所有分支的最大步数.

定理 对每个时间为 $t(n)$ 的 NTM, 都有一个等价的时间为 $2^{O(t(n))}$ 的 TM.