• 运行时间建模
  • 学习目标
  • 13.1 形式化的定义运行时间
    • 13.1.1 多项式时间和指数时间
  • 13.2 使用 RAM 机 / NAND-RAM 建模运行时间
  • 13.3 扩展Church-Turing论题 (讨论)
  • 13.4 高效的通用机器: 在 NAND-RAM 中的 NAND-RAM 解释器
    • 13.4.1 限时通用图灵机
  • 13.5 时间层级定理 (Time Hierarchy Theorem)
  • 13.6 非一致性计算
    • 13.6.1 非感知的 NAND-TM 程序
    • 13.6.2 “循环展开”: 从图灵机到电路的转换算法
    • 13.6.3 一致性算法可以模拟非一致性算法吗?
    • 13.6.4 一致性与非一致性计算: 总结
  • 13.7 习题
  • 13.8 参考文献

运行时间建模

学习目标

• 形式化的建模程序的运行时间, 特别是诸如 $O(n)$ 或 $O(n^3)$ 时间算法的概念
• 分别对多项式时间和指数时间进行建模的复杂性类 $\mathbf{P}$ 和 $\mathbf{EXP}.$
• 了解时间层级定理, 即对于任意 $k\ge 1$ 都存在我们可以在 $O(n^{k+1})$ 时间计算但不能在 $O(n^k)$ 时间计算的函数.
• 代表非一致性计算 ${\mathbf{P}}_{/poly}$ 的复杂性类, 及 $\mathbf{P}\subseteq {\mathbf{P}}_{/poly}$ 这一结论.

在 第12章 中, 我们介绍了一些高效的算法, 并且对他们的运行时间做了一些假设, 不过并未对这些算法的运行时间进行精确数学定义. 我们将在本章节中借助我们之前已经介绍过的图灵机和 RAM（或等价的 NAND-TM 和 NAND-RAM）机完成这一工作. 任何非平凡的算法都会在更大规模的输入上运行更长的时间, 因此算法的运行时间并不能用一个确定的数字来表示. 因此, 我们想要确定的是算法需要运行的步数和输入长度的关系. 我们特别关注以下两者之间的区别, 那些最多只需多项式时间（即对于某个常数 $c,$ 时间为 $O(n^c)$）的算法, 与那些任何算法都至少需要指数时间（即对于某个 $c,$ 时间为 $\Omega (2^{n^c})$）的问题. 正如 第12章 中 Edmonds 的引言所提到的, 这两者之间的差异, 有时与可计算和不可计算之间的差异一样重要.

要将这一切用不那么数学化的语言表述出来, 我们将定义能在 $T(n)$ 步内将函数 $F:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ 计算出来的含义, 其中 $T$ 是一个将输入长度 $n$ 映射到计算所需的步数的函数. 使用这些定义, 我们将做以下事情（可参考 图 13.1）

• 我们定义复杂性类 $\mathbf{P}$ 为可以在多项式时间内计算的布尔函数的集合, 复杂性类 $\mathbf{EXP}$ 为可以在指数时间内计算的函数的集合. 注意 $\mathbf{P}\subseteq \mathbf{EXP},$ 即如果我们能在多项式时间内计算一个函数, 那么当然也能在指数时间内计算他.

• 我们证明, 用图灵机和RAM机计算一个函数所需的时间是多项式相关的. 这意味着, 无论使用图灵机还是 RAM 机（或 NAND-RAM 机）来定义, $\mathbf{P}$ 和 $\mathbf{EXP}$ 总是相同.

• 我们给出一个高效且通用的 NAND-RAM 程序, 并使用它建立时间层级定理, 该定理意味着 $\mathbf{P}$ 是 $\mathbf{EXP}$ 的真子集.

• 我们将此处定义的概念与 第3章 中定义的布尔电路和 NAND-CIRC 程序等非一致性模型联系起来. 我们将 ${\mathbf{P}}_{/poly}$ 定义为可以由一系列多项式大小的电路所计算的函数类. 我们证明了 $\mathbf{P}\subseteq {\mathbf{P}}_{/poly},$ 且 ${\mathbf{P}}_{/poly}$ 包含不可计算函数.

13.1 形式化的定义运行时间

我们的计算模型（图灵机, NAND-TM 和 NAND-RAM 程序等）都是通过其运作方式都是对输入逐步执行一系列指令. 我们可以通过测量算法 $M$ 在输入 $x$ 上执行的步数, 并将其表示为输入长度 $|x|$ 的函数, 从而定义算法 $M$ 在这些模型下的运行时间. 我们首先定义基于图灵机的运行时间：

放宽条件只考虑充分大的 $n$ 虽然本质上并不是很重要, 但却非常便利, 因为这使我们能够避免讨论一些无趣的边界情况. 尽管“函数的运行时间”这一概念可以在任意函数上定义, 但在定义 $TIM{E}_{\mathsf{TM}}(T(n))$ 类时, 我们只考虑布尔函数, 即那些只有一个 bit 输出的函数. 这一选择并不重要, 是为了后续讨论的简洁与便利而做出的. 事实上, 任何一个非布尔函数都有一个与之计算等价的布尔变体, 参见 习题 13.3

13.1.1 多项式时间和指数时间

与可计算性的概念不同, 精确的运行时间可能会取决于我们所使用的计算模型. 然而, 事实上, 如果我们只关心“足够粗糙”的尺度（大部分情况下都是如此）, 那么模型的选择——无论是图灵机、RAM 机、NAND-TM/NAND-RAM 程序, 还是 C/Python 程序——都无关紧要了. 这就是所谓的扩展Church-Turing论题 (extended Church-Turing Thesis). 具体来说, 我们主要关心的是多项式时间与指数时间之前的区别.

我们将关注以下两个主要的时间复杂性类:

• 多项式时间: 如果一个函数 $F:\{0,1{\}}^{\ast }\to \{0,1\}$ 属于类 $\mathbf{P}={\cup }_{c\in \{1,2,3,\dots \}}TIM{E}_{\mathsf{TM}}(n^c),$ 则称其是 多项式时间可计算 的. 也就是说, 若 $F\in \mathbf{P},$ 则存在一个计算 $F$ 的算法, 其运行时间关于输入长度至多是多项式的（换言之, 对于某个常数 $c,$ 至多 $n^c$）.

• 指数时间: 如果一个函数 $F:\{0,1{\}}^{\ast }\to \{0,1\}$ 属于类 $\mathbf{EXP}={\cup }_{c\in \{1,2,3,\dots \}}TIM{E}_{\mathsf{TM}}(2^{n^c}),$ 则称其是 指数时间可计算 的. 也就是说, 若 $F\in \mathbf{EXP},$ 则存在一个计算 $F$ 的算法, 其运行时间关于输入长度至多是指数的（换言之, 对于某个常数 $c,$ 至多 $2^{n^c}$）.

形式化的说, 他们是如下定义的.

因为指数时间比多项式时间大得多, $\mathbf{P}\subseteq \mathbf{EXP}$ 类. 我们在 第12章 中列出的所有问题都属于 $\mathbf{EXP},$ 不过如我们所见, 对于他们中的一些问题存在更高效的算法，这证明了他们实际上属于更小的 $\mathbf{P}$ 类.

13.2 使用 RAM 机 / NAND-RAM 建模运行时间

图灵机虽然是一种简洁的理论计算模型, 但它与现实世界的计算架构并不十分吻合. 当我们考虑哪些函数是“可计算的“这一问题时, 图灵机与实际计算机之间的这种差异关系不大; 但在涉及“效率“的语境下, 这种差异就会产生影响. 甚至是本科算法课程中的基础内容——如“归并排序“, 也无法在图灵机上以 $O(n\log n)$ 的时间实现 (参见 参考文献). RAM 机 (或等价的 NAND-RAM 程序) 更接近实际的计算架构, 也更符合我们在算法课程或白板编程面试中所说的 $O(n)$ 或 $O(n\log n)$ 算法的含义. 我们可以像定义图灵机那样, 定义针对 NAND-RAM 程序的运行时间.

因为 NAND-RAM 程序更加符合我们对运行时间的直观理解, 我们将把 NAND-RAM 作为我们讨论运行时间的默认模型, 并因此使用不带任何下标的 $TIME(T(n))$ 来表示 $TIM{E}_{\mathsf{RAM}}(T(n)).$ 然而, 事实证明, 只要我们只关心指数时间和多项式时间之间的区别, 模型的选择并没有太大影响. 原因是图灵机可以模拟 NAND-RAM 程序, 且其开销至多是多项式级别的 (参见 图 13.4):

例如, 通过将 $T(n)=n^a$ 代入 定理 13.1, 并利用 $10n^a=o(n^{a+1})$ 这一事实, 我们看到 $TIM{E}_{\mathsf{TM}}(n^a)\subseteq TIM{E}_{\mathsf{RAM}}(n^{a+1})\subseteq TIM{E}_{\mathsf{TM}}(n^{4a+4}).$ 这意味着 (根据 练习 13.2): $$\mathbf{P}={\cup }_{a=1,2,\dots }TIM{E}_{\mathsf{TM}}(n^a)={\cup }_{a=1,2,\dots }TIM{E}_{\mathsf{RAM}}(n^a).$$ 也就是说, 我们完全可以将 $\mathbf{P}$ 定义为由 NAND-RAM 程序 (而不是图灵机) 在输入长度的多项式时间内计算的函数类. 同样地, 通过将 $T(n)=2^{n^a}$ 代入 定理 13.1, 我们看到 $\mathbf{EXP}$ 类也可以定义为由 NAND-RAM 程序在至多 $2^{p(n)}$ 时间内计算的函数集, 其中 $p$ 为某个多项式. 对于许多其他模型, 包括元胞自动机, C/Python/Javascript 程序, 并行计算机以及许多其他模型, 已知都存在类似的等价结果. 这证明了选择 $\mathbf{P}$ 作为捕捉独立于技术的“易处理性“概念是合理的 (参见 13.3 节 关于此问题的更多讨论). 图灵机和 NAND-RAM (以及其他模型) 之间的这种等价性, 允许我们根据手头的任务选择我们最喜欢的模型 (即“鱼与熊掌兼得“), 即使在研究效率问题时也是如此—只要我们只关心多项式时间和指数时间之间的差距. 当我们想要设计一个算法时, 我们可以利用 NAND-RAM 提供的额外能力和便利. 当我们想要分析一个程序或证明一个否定性结果时, 我们可以将注意力局限于图灵机.

上文中的形容词 “合理的” 指的是所有已实现的、可扩展的计算模型, 而 量子计算机 可能是唯一的例外. 参见 13.3 节 和 第23章.

13.3 扩展Church-Turing论题 (讨论)

定理 13.1 表明, 图灵机和 RAM 机/ NAND-RAM 程序这几个计算模型在运行时间上是多项式等价的. 其他多项式等价模型的例子有:

• 所有标准的编程语言, 包括 C/Python/JavaScript/Lisp/等.
• $\lambda$ 算子 (参见 13.8 节)
• 元胞自动机
• 并行计算机
• 生物计算设备, 如基于 DNA 的计算机.

扩展Church-Turing论题 指出, 这一表述对于所有物理上可实现的计算模型均成立. 换言之, 扩展Church-Turing论题认为, 对于任意一个可以扩展的计算设备 $C$ (该设备具有有限的描述, 但原则上可以用于处理任意长度的输入), 都存在某个常数 $a,$ 使得对于 $C$ 在长度为 $n$ 的输入上使用 $S(n)$ 量的物理资源所能计算的每一个函数 $F:\{0,1{\}}^{\ast }\to \{0,1\},$ $F$ 都属于 $TIME(S(n{)}^a).$ 这是对一般的Church-Turing论题 (在 第 8.8 节 中被讨论) 的加强. 普通论题仅指出所有物理上可实现模型的“可计算函数集“是相同的, 但不要求不同模型之间模拟的开销至多为多项式级别.

目前所有关于可扩展计算模型和编程语言的构建都遵循扩展Church-Turing论题, 即它们都可以被图灵机 (以及 NAND-TM 或 NAND-RAM 程序) 以多项式级开销进行模拟. 因此, $\mathbf{P}$ 和 $\mathbf{EXP}$ 类对于模型的选择具有鲁棒性. 我们可以使用任何我们喜欢的编程语言, 或者算法的高层描述, 来确定一个问题是否属于 $\mathbf{P}.$

与Church-Turing论题本身一样, 扩展Church-Turing论题也处于渐近设定之下, 并不直接产生可实验验证的预测. 然而, 它可以用更具体的开销界限来实例化, 从而产生可实验验证的预测, 例如我们在 5.6 节 中提到的物理扩展Church-Turing论题.

在过去一百多年对计算的研究和机械化进程中, 尚未有人制造出能违反扩展Church-Turing论题的可扩展计算设备. 然而, 量子计算 (如果得以实现) 将对扩展丘奇-图灵论题提出严峻挑战 (见 第23章). 但是, 即便量子计算的愿景完全实现, 扩展Church-Turing论题在“精神层面“上依然是正确的: 虽然我们需要修正该论题以纳入量子计算的可能性, 但其宏观框架保持不变. 我们依然能够对计算进行数学建模; 依然可以将程序视为字符串并拥有通用程序; 依然拥有时间层级和不可计算性结果; 并且依然没有理由怀疑 (“普通”) Church-Turing论题. 此外, 量子计算的前景似乎并不会改变我们所关心的许多 (虽非全部!) 具体问题的运行时间复杂度. 特别是, 就我们目前所知, 在 第12章 提到的所有示例问题中, 只有整数分解这一个问题的复杂度, 会因为将模型修改为包含量子计算机而受到影响.

13.4 高效的通用机器: 在 NAND-RAM 中的 NAND-RAM 解释器

我们已经在 定理 9.1 中见过了 “通用图灵机”. 审视其证明, 并结合 定理 13.1 , 我们可以看到程序 $U$ 具有多项式开销, 即它可以在 $O(T^4)$ 步内模拟给定 NAND-TM (或 NAND-RAM) 程序 $P$ 在输入 $x$ 上运行 $T$ 步. 但事实上, 通过直接模拟 NAND-RAM 程序, 我们可以做的更好, 仅需常数倍的乘法开销. 也就是说, 存在一个通用 NAND-RAM 程序 $U,$ 使得对于每一个 NAND-RAM 程序 $P,$ $U$ 仅需要 $O(T)$ 步就能模拟 $P$ 的 $T$ 步. ($O$ 记号中隐含的常数可能取决于程序 $P,$ 但不依赖输入的长度.)

13.4.1 限时通用图灵机

高效通用机的一个推论如下. 给定任意图灵机 $M,$ 输入 $x,$ 以及 “步数预算” $T,$ 我们可以在关于 $T$ 的多项式时间内模拟 $M$ 执行 $T$ 步. 形式化地, 我们定义一个函数 $TIMEDEVAL,$ 它接受 $M,$ $x$ 和时间预算这三个参数, 如果 $M$ 在至多 $T$ 步内停机, 则输出 $M(x),$ 否则输出 $0.$ 限时通用图灵机在多项式时间内计算 $TIMEDEVAL$ (见 图 13.6). (由于我们将时间作为输入长度的函数来度量, 我们将 $TIMEDEVAL$ 定义为接受以 一元 表示的输入 $T:$ 即由 $T$ 个 1 组成的字符串.)

13.5 时间层级定理 (Time Hierarchy Theorem)

一些函数是不可被计算的, 但是否存在可被计算, 但只能以很高的代价计算的函数呢? 具体来说, 是否存在能在 $2^n$ 时间内被计算, 但不能在 $2^{0.9n}$ 时间内被计算的函数呢? 事实证明, 这个问题的答案为是.

这里出现 $\log n$ 并没有什么特殊的理由, 我们也可以用其他能被高效计算, 且当 n 趋于无穷时也趋于无穷的函数来替代 $\log n.$

时间层级定理告诉我们, 存在一些函数我们能在 $O(n^2)$ 时间计算但不能在 $O(n)$ 时间计算, 能在 $2^n$ 时间计算但不能在 $2^{\sqrt{n}}$ 时间计算, 等等.. 特别的, 肯定存在一些函数我们能在 $2^n$ 时间计算但不能在 $O(n)$ 时间计算. 我们已经见过了太多自然的函数, 其已知的最好算法需要大约 $2^n$ 的时间, 且已经有许多人投入了大量的时间与精力来尝试改进这些问题的算法. 然而, 不像有穷对无穷那样, 上述的所有例子, 我们目前仍然不知道如何去排除有 $O(n)$ 时间的算法存在.
然而我们将看到, 存在一个未被证明的猜想表明大多数这类问题都有这样的结论.

时间层级定理的存在依赖于高效通用 NAND-RAM 程序 (已在 定理 13.2 被证明存在). 对于其他计算模型, 如图灵机, 我们有类似的时间层级定理表明存在某个函数能在 $T(n)$ 时间内被计算但不能在 $T(n)/f(n)$ 时间内被计算, 其中 $f(n)$ 对应于相应通用机器的开销.

13.6 非一致性计算

我们现在已经了解过了两种 “计算代价” 的度量. 在 4.6 节 中, 我们使用电路 / 直线式程序定义了计算有限函数的复杂性. 具体来说, 对于有限函数 $g:\{0,1{\}}^n\to \{0,1\}$ 和数 $s\in \mathbb{N},$ 如果存在一个至多包含 $s$ 个与非门的电路 (或一个等价的 $s$ 行的 NAND-CIRC 程序) 来计算 $g,$ 则 $g\in SIZ{E}_n(s).$ 为了将其与本章定义的类 $TIME(T(n))$ 联系起来, 我们首先需要将类 $SIZ{E}_n(s)$ 扩展到具有无界输入长度的函数.

换言之, $F\in SIZE(T)$ 当且仅当对于任意 $n\in \mathbb{N},$ $F_{\upharpoonright n}\in SIZ{E}_n(T(n)).$ 类 $\mathbf{P}$ 在非一致性中的类似物是 ${\mathbf{P}}_{/poly},$ 其被定义为

$${\mathbf{P}}_{/poly}={\cup }_{c\in \mathbb{N}}SIZE(n^c).\text{\hspace{1em}(13.2)}$$

非一致性计算与一致性复杂性类 (如 $TIME(T(n))$ 或 $\mathbf{P})$ 之间存在巨大差异. $F\in \mathbf{P}$ 意味着存在一个固定的 (不由输入改变) 图灵机 $M$ 满足在任意输入上, $M$ 都能以多项式时间计算 $F$ 的结果. 而 $F\in {\mathbf{P}}_{/poly}$ 仅意味着, 对于每个输入长度 $n,$ 存在一个不同的 (可能由输入大小改变) 的电路, 使用多项式数量的门来计算该长度输入上的 $F.$ 正如我们所见, $F\in {\mathbf{P}}_{/poly}$ 并不意味着 $F\in \mathbf{P}.$ 然而, 这一陈述的反方向是成立的.

特别的, 定理 13.5 表明对于每个 $c,$ $TIME(n^c)\subseteq SIZE(n^{ca}),$ 因此 $\mathbf{P}\subseteq {\mathbf{P}}_{/poly}.$

for i in range(4):
	print(i)

print(0)
print(1)
print(2)
print(3)

13.6.1 非感知的 NAND-TM 程序

我们证明 定理 13.5 的方法涉及了 “循环展开”. 比如, 考虑下面这个用于计算任意输入长度 $XOR$ 函数的 NAND-TM 程序:

temp_0 = NAND(X[0],X[0])
Y_nonblank[0] = NAND(X[0],temp_0)
temp_2 = NAND(X[i],Y[0])
temp_3 = NAND(X[i],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
MODANDJUMP(X_nonblank[i],X_nonblank[i])

举个例子, 若 $n=3,$ 我们可以尝试通过简单地把循环复制三遍 (删去 MODANDJMP 这行), 把这个 NAND-TM 程序翻译成用于计算 $XO{R}_3:\{0,1{\}}^3\to \{0,1\}$ 的 NAND-CIRC 程序

temp_0 = NAND(X[0],X[0])
Y_nonblank[0] = NAND(X[0],temp_0)
temp_2 = NAND(X[i],Y[0])
temp_3 = NAND(X[i],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
temp_0 = NAND(X[0],X[0])
Y_nonblank[0] = NAND(X[0],temp_0)
temp_2 = NAND(X[i],Y[0])
temp_3 = NAND(X[i],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
temp_0 = NAND(X[0],X[0])
Y_nonblank[0] = NAND(X[0],temp_0)
temp_2 = NAND(X[i],Y[0])
temp_3 = NAND(X[i],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)

然而, 上面这个仍然不是一个合法的 NAND-CIRC 程序, 因为它包含一个对特殊变量 i 的引用. 我们可以通过将第一个迭代中的 i 替换为 $0,$ 第二个迭代中的替换为 $1,$ 第三个迭代中的替换为 $2$ 来把上述程序转化为一个合法的 NAND-CIRC 程序. (我们还创建了一个变量 zero, 并在任意变量第一次初始化时使用, 同时移除了那些后续不再使用的非输出变量的赋值) 结果程序是一个标准的计算 $XO{R}_3$ 的 “无索引无循环” 的 NAND-CIRC 程序. (另见 图 13.10)

temp_0 = NAND(X[0],X[0])
one = NAND(X[0],temp_0)
zero = NAND(one,one)
temp_2 = NAND(X[0],zero)
temp_3 = NAND(X[0],temp_2)
temp_4 = NAND(zero,temp_2)
Y[0] = NAND(temp_3,temp_4)
temp_2 = NAND(X[1],Y[0])
temp_3 = NAND(X[1],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
temp_2 = NAND(X[2],Y[0])
temp_3 = NAND(X[2],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)

这种转换的关键在于, 在我们最初的 $XOR$ NAND-TM 程序中, 无论输入是 $011,$ $100$ 还是任何其他字符串, 索引变量 i 都保证在第一次迭代中等于 $0,$ 在第二次迭代中等于 $1,$ 在第三次迭代中等于 $2,$ 依此类推. 特定的序列 $0,1,2,\dots$ 并不重要: 关键属性在于 $XOR$ 的 NAND-TM 程序是 非感知的, 即在第 $j$ 次迭代中索引 i 的值仅取决于 $j,$ 而不取决于输入的具体选择. 幸运的是, 我们能够将每个 NAND-TM 程序转换为功能等效的非感知程序, 且其开销至多为二次方. (类似地, 我们可以将任何图灵机转换为功能等效的非感知图灵机, 参见 习题 13.6)

换言之, 定理 13.6 意味着如果我们能在 $T(n)$ 步内计算 $F,$ 那么我们就能用一个程序 $P$ 在 $O(T(n{)}^2)$ 步内计算它, 且变量 i 在第 $j$ 次迭代中的值只取决于 $j$ 和输入的长度, 不依赖于输入的内容. 这样的程序可以通过 “循环展开” 轻松的被转译成 $O(T(n{)}^2)$ 行的 NAND-CIRC 程序.

定理 13.6 能导出 定理 13.5. 事实上, 如果 $P$ 是一个 $k$ 行的非感知的在 $T(n)$ 时间内计算 $F$ 的 NAND-TM 程序, 那么对于每个 $n,$ 只需要简单的做 $T(n)$ 次复制黏贴 (删去 MODANDJMP 指令), 我们都可以得到一个 $(k-1)\cdot T(n)$ NAND-CIRC 程序. 在第 $j$ 个副本中, 我们将所有形为 Foo[i] 的引用替换为 foo_$i_j,$ 其中 $i_j$ 是 i 在第 $j$ 次迭代中的值.

13.6.2 “循环展开”: 从图灵机到电路的转换算法

定理 13.5 的证明是 算法的, 即这个证明给出了一个多项式时间的算法能够在给出一个图灵机 $M,$ 参数 $T$ 和 $n$ 的前提下生成一个有 $O(T^2)$ 个门的电路, 且这个电路在任意输入 $x\in \{0,1{\}}^n$ 上运行的结果都与 $M$ 一致 (只要 $M$ 在这些输入上的运行步数少于 $T.$) 我们将在下面的定理中记录这一事实, 因为这之后会对我们很有用.

13.6.3 一致性算法可以模拟非一致性算法吗?

定理 13.5 向我们展示了每个属于 $TIME(T(n))$ 的函数都属于 $SIZE(poly(T(n))).$ 有人可能会问是否存在一个反向的关系. 假设有一个 $F,$ 满足对于每个 $n,$ 其 $F_{\upharpoonright n}$ 都有一个 “短的” NAND-CIRC 程序. 我们能说对于某些 “小的” $T$ 它一定在 $TIME(T(n))$ 中吗? 答案是坚决的 不. 不仅 ${\mathbf{P}}_{/poly}$ 不包含在 $\mathbf{P}$ 中, 事实上, ${\mathbf{P}}_{/poly}$ 中存在一些函数 无法计算.

这里的问题显然是 一致性. 对于一个函数 $F:\{0,1{\}}^{\ast }\to \{0,1\},$ 如果 $F$ 属于 $TIME(T(n)),$ 那么我们有 单一 的算法可以对于每个 $n$ 计算 $F_{\upharpoonright n}.$ 另一方面, 对于每个 $n,$ $F_{\upharpoonright n}$ 可能都在 $SIZE(T(n))$ 中, 但对每个输入长度使用完全不同的算法. 因此, 我们通常不将 ${\mathbf{P}}_{/poly}$ 用作 高效 计算的模型, 而是用来建模 低效计算. 例如, 在密码学中, 人们通常将一个加密方案是安全的定义为: 破解长度为 $n$ 的密钥需要超过多项式数量的 NAND 行. 由于 $\mathbf{P}\subseteq {\mathbf{P}}_{/poly},$ 这特别排除了用于破解的多项式时间算法, 但在密码学中使用非一致性模型还有技术上的原因. 它也允许用非渐进术语来谈论安全性, 例如方案具有 “$128$ 位安全性”.

虽然这有时可能是一个真正的问题, 但在许多自然的背景下, 一致性和非一致性计算之间的差异似乎并不那么重要. 特别的, 在我们之前讨论的所有未知是否在 $\mathbf{P}$ 中的问题示例中: 最长路径, 3SAT, 因数分解等, 这些问题也都不知道是否在 ${\mathbf{P}}_{/poly}$ 中. 因此, 对于 “自然的” 函数, 如果你假装 $TIME(T(n))$ 大致等同于 $SIZE(T(n)),$ 你正确的概率通常比错误的要大.

13.6.4 一致性与非一致性计算: 总结

总而言之, 我们目前描述的两种计算模型是:

• 一致性模型 (Uniform models): 图灵机, NAND-TM 程序, RAM 机器, NAND-RAM 程序, C/JavaScript/Python 等. 这些模型包含循环和无界内存, 因此单个程序可以计算具有无界输入长度的函数.

• 非一致性模型 (Non-uniform models): 布尔电路 或 直线程序 没有循环, 只能计算有限函数. 执行它们的时间恰好是它们包含的行数或门的数量.

对于一个函数 $F:\{0,1{\}}^{\ast }\to \{0,1\}$ 和某个良好的时间界限 $T:\mathbb{N}\to \mathbb{N},$ 我们知道:

• 如果 $F$ 在时间 $T(n)$ 内是一致可计算的, 那么存在一系列电路 $C_1,C_2,\dots ,$ 其中 $C_n$ 具有 $poly(T(n))$ 个门并且对每个 $n$ 计算 $F_{\upharpoonright n}$ (即, $F$ 对 $\{0,1{\}}^n$ 的限制).

• 反之不一定成立 - 存在函数 $F:\{0,1{\}}^n\to \{0,1\}$ 的例子, 使得 $F_{\upharpoonright n}$ 甚至可以由常数大小的电路计算, 但 $F$ 是不可计算的.

这意味着非一致性复杂度对于建立函数的 困难性 比建立其 容易性 更有用.

13.7 习题