复杂度理论所关心的,是资源如何随输入长度增长,而不是某台特定的笔记本电脑在某个输入上花多长时间。在度量一个计算之前,我们必须明确什么算作输入、什么算作答案、什么算作一步。精确的模型还会揭示一个更根本的局限:有些判定问题根本不存在任何算法。
为什么先要有资源与模型
像“这个算法很快”这样的陈述,在三件事被固定之前没有任何数学内容:算法接收的对象、它可以执行的操作,以及被计数的量。复杂度理论一次性固定这些选择,使得关于不同问题的陈述变得可以比较,也使得关于所有算法的定理成为可能。形如“没有算法能做到 X”的定理,是对任何人可能写出的每一个程序进行量化。只有当“算法”被赋予了足够精确、可以据以推理的定义时,这样的陈述才有意义。
本单元有两个目标及一篇续篇。第一,定义判定问题、确定型计算与时间界限,并准确地看清为什么输入的编码属于问题的一部分。第二,用两种不同的论证证明不可判定语言的存在:一个计数论证表明它们为数众多,一个对角构造则给出一个具体的例子。续篇把对角思想用于可计算的时间截断,并说明证明层级定理还需要哪些工作。
关于这里证明了什么的说明。凡标为定理或命题的内容,在本单元中都有完整的证明,除非某个陈述被明确标注为未证明的依赖项。标准机器模型之间具有多项式开销的模拟,以及试除例题中的 Bertrand 公设,均不加证明地使用。
模型与判定
定义 4.1.1
(语言与确定型计算)
固定一个有限字母表,例如 。语言 是有限字符串的一个集合。若一台确定型图灵(Turing)机在每个输入上都停机,并且恰好接受 中的字符串,则称它判定 。它在某个输入上的时间是直到停机为止的步数;它在长度 上的最坏情形时间是所有长度为 的输入上的最大值。类 包含那些可由确定型机器在以输入长度的多项式为界的时间内判定的语言。
编码是问题的一部分。例如,二进制整数 的长度约为 ,因此一个需要 步的算法不一定在输入长度的多项式时间内运行。合理的确定型机器模型之间在时间上可以以多项式开销相互模拟,所以类 在标准的模型更换下是稳健的;这一模拟事实在此不加证明地使用。然而,精确的运行时间指数仍可能依赖于模型。
判定问题就输入提出一个“是或否”的问题,而语言则把该问题打包成答案为“是”的输入所构成的集合。就本单元的目的而言,限制为“是或否”的答案不会丢失任何东西。计算一个函数可以改写为判定一个由输入—输出对构成的语言,而我们所研究的困难性现象在这种最简单的情形中就已经出现。
还需要两个概念。若一台机器接受 的每一个字符串,并且不接受 之外的任何字符串,则称它识别语言 。对于 之外的字符串,它可以拒绝,也可以永远运行。每个判定器都是识别器,但反过来不成立,停机问题将说明这一点。若某台机器判定一个语言,则称该语言可判定;若某台机器识别它,则称它可识别。
时间界限与类 P
定义 4.1.2
(在时间界限内的判定)
设 为一个函数。若一台确定型图灵机判定 ,并且对每个 以及每个长度为 的输入 ,它至多在 步之后停机,则称它在时间 内判定 。类 由以下语言构成:存在一台在每个输入上均停机的判定机器及常数 ,使得对所有充分大的输入长度,其运行步数至多为 。于是 ,这与上文的定义一致,因为一旦 ,一个多项式就以某个 和 为界,被 所界定。
最坏情形的约定很重要。一台在大多数输入上都很快、但在每个长度的某一个输入上需要 步的机器,其最坏情形时间为 ,而这正是定义所记录的量。平均情形的行为是另一个主题,这里不予度量。
多项式时间之所以占据核心地位,部分原因在于它对复合封闭。如果一个多项式时间的过程为另一个过程准备输入,则两者的组合仍然是多项式时间。下面的命题把这一点精确化,其证明用到了一个容易被忽视的观察:一台机器写下的符号数不可能多于它的步数。
命题 4.1.3
(多项式预处理保持 P)
设 是从字符串到字符串的函数,由一台确定型图灵机在长度为 的输入上至多 的时间内计算;设 在长度为 的输入上至多 的时间内被判定,其中 与 是系数非负的多项式。则 可在多项式时间内被判定;因此 。
证明
(复合界限的证明)
对长度为 的输入 ,首先运行计算 的机器。它在 步之内停机。在每一步中它至多访问一个新的带格,而输入已经占用 个带格,因此至多访问 个带格,输出 的长度 。然后在 上运行 的判定器。其运行时间至多为 。由于 的系数非负,它是不减的,所以 。该机器恰好在 时接受。在标准的单带模型上,用多项式步数来整理并定位输出,例如至多为 的一个常数倍。这两个阶段与此转移代价具有一个多项式界。
如果没有关于输出长度的观察,对粗心的读者而言,该命题按原样陈述将是错误的。一个速度很快但产生巨大输出的第一阶段,会使第二阶段变得代价高昂。证明表明这不可能发生:输出长度受运行时间控制。
编码与输入长度
本节的核心告诫是:仅仅由于输入的书写方式不同,同一个过程可以是高效的,也可以是低效的。上文已经用过的下面这个例子是典型的模型案例。
例题 4.1.4
(输入规模改变界限)
对一个正整数 反复做减一操作需要 次迭代。如果 用 位二进制书写,则 可以大到 ;因此该过程在 上有指数级的最坏情形迭代次数。若输入为一进制 ,则同样的次数相对于输入长度是线性的。这是不同的编码,因而是不同的复杂度陈述。
下一个例子对一个看起来无害的过程——试除法——进行精确计数。
例题 4.1.5
(试除法关于二进制位长是指数级的)
考虑如下过程:给定二进制整数 ,对每个满足 的 进行检验,若某个 整除 ,则宣告 为合数。取 ,它有 位。由于 且 ,我们得到 。因此,只要之前没有找到因子,该过程就要检验 个除数。(这个特定的 是素数,所以全部 次检验都会执行。)
对一般的 ,设最高位为 ,从而 。于是 ,而素数输入迫使至少进行 次除法。对 ,这个下界是 ,与上面的精确计数一致。对 ,这个下界是 ,超过十亿次除法。根据Bertrand 公设(此处不加证明地使用),对每个 都存在 位素数;因此最坏情形的除法次数是 。现在把编码改为一进制,使输入长度为 。除法次数至多为 ,每次代价为 的多项式,所以同一个过程在 上以多项式时间运行。算法没有改变;改变的是输入规模的度量。(已知的一个定理是:素性在二进制编码下存在多项式时间算法,但那是一个不同的、聪明得多的算法,本单元中没有任何内容依赖于它。)
教益在于,“关于数的多项式”与“关于数的长度的多项式”是不同的概念,而复杂度理论默认指的是后者。代价关于数值是多项式、关于位长是指数的过程,有时被称为伪多项式的,每当整数出现在输入中时,它们都会再次出现。
例题 4.1.6
(同一数值的两种编码)
整数 的二进制表示是 ,因此二进制输入长度为四。将它不断减一直至零的循环执行十三次;由 得 。一进制输入则是十三个一构成的串,同样的十三次迭代对该输入长度是线性的。算术数值没有改变,但复杂度陈述中的规模参数不同。一个例子不能证明渐近界,却能说明最坏情形分析中应让哪个量变化。
计数:大多数语言是不可判定的
在给出一个显式的不可判定语言之前,我们说明不可判定语言必定存在,其理由纯粹是数量上的:语言太多,而机器太少。
命题 4.1.7
(不可判定语言存在)
图灵机只有可数多个,因此 上的可判定语言只有可数多个。 上所有语言构成的集合是不可数的。因此 上存在某个语言是不可判定的。
证明
(计数与康托尔(Cantor)对角化证明)
每台图灵机都有一个有限的描述(它的状态、字母表和转移表),可以写成某个固定有限字母表上的有限字符串。有限字母表上的有限字符串的集合是可数的:按长度递增列出,同一长度内按字母顺序排列。因此这些机器可以列为 ,而每台机器至多判定一个语言。所以可判定语言都包含在某个列表 中(对于不判定任何语言的机器,重复一个固定的可判定语言,例如空集)。
现在以同样的先按长度、再按字母顺序,把所有二进制字符串列为 ,并定义
对每个 ,语言 与 在字符串 上不一致,所以 。因此 不出现在列表中的任何位置,特别地它不是可判定的。将同样的论证应用于任何给定的语言列表,可知没有任何列表包含所有语言,因此语言的集合是不可数的。
这一论证是纯粹的存在性证明。它没有说明哪些语言是不可判定的,并且正确地暗示了:“典型”的语言是不可判定的,而可判定的语言是例外。它还预示了下一节的机制:字符串 被用来让第 台机器查询关于它自己的问题,然后将答案反转。
一个不可判定问题
定理 4.1.8
(停机语言是不可判定的)
设 ,其中使用对机器与输入的有效编码。没有任何确定型图灵机判定 。
证明
(对角证明)
假设存在判定器 。构造一台机器 ,它在输入编码 时,在 上运行 。如果 说 在其自身的编码上停机,则 永远循环;否则 停机。现在在 上运行 。如果它停机,则 的正确答案迫使它循环;如果它循环,则正确答案迫使它停机。两种情形都与所假设的 的正确性相矛盾。
证明透视
自指用到了什么,又忽略了什么
论证依靠三件事。第一,假设 是判定器,所以它在每个输入上都停机, 是一台定义明确的机器;全函数性(totality)正是在这里被用上。第二,编码是有效的: 可以机械地由 算出 。第三,唯一不显然的一步,是把 自己的描述输入给 ,使 对 的回答,恰好是 被构造来反驳的内容: 在 上停机,当且仅当 报告 在 上不停机。由于 的报告按假设是正确的,矛盾便成立;其余每一步都是机械的构造,所以唯一可能出错的就是 的存在。若 只是识别器,论证就毫无结果:当 在 上不停机时, 自己也可能不停机,于是 同样不停机,并无矛盾,这与 可被识别是一致的。
这一矛盾并不是说没有任何特定的机器—输入对可以被分析。它说的是,不存在一个全函数式的算法能够正确地解决每一个被编码的对。 的识别器确实存在:模拟 在 上的运行,若它停机就接受,但这个识别器在非成员上会永远运行。判定要求在“是”和“否”两类实例上都停机。
反例模式
模拟器不是判定器
断言:模拟 在 上的运行、并在模拟停机时接受的机器 能判定 ,因为只要它作出回答,答案就是正确的。反例:令 为只有一个状态的机器,其唯一的转移是在每个符号(包括空白符)上把读写头向右移一格,并且没有停机状态。在输入 上,模拟永远不会完成,所以 既不接受也不拒绝。这个对不属于 ,判定器必须停机并拒绝它。因此 识别 ,却没有判定它。补救的办法不是更巧妙的模拟器:上述定理表明,没有任何机器能在所有的对上正确地停机。
常见错误
(不可判定与代价高昂)
指数时间的算法仍然是在每个输入上都停机的算法。不可判定性排除的是每一个判定器,无论其时间界限如何;它并不仅仅是在声称最好的算法很慢。
概念视角结构
可判定即两侧皆可识别
一个语言可判定,当且仅当它和它的补集都可识别:让两个识别器交替运行、每次各走一步,恰有一个最终会接受。因此, 可识别但不可判定,它的补集便不可识别。
练习与解答
快速检查
(一个过程在 的二进制编码上运行 次迭代。请给出作为位长 的函数的最坏情形界限。)
解答 · 答案
由于 ,迭代次数小于 ;接近 的输入表现出指数级的最坏情形。
快速检查
(解释为什么对 在 上的模拟识别了 却并不判定它。)
解答 · 答案
如果 停机,模拟最终会观察到这一点并接受。如果 永不停机,模拟永远不会结束,因此它不满足判定器必须在每个输入上停机的要求。
快速检查
(一个试除过程对一个有 位且最高位为 的二进制整数 ,检验所有满足 的 。证明:只要 在该范围内没有因子,就至少执行 次除法。)
解答 · 答案
最高位为 给出 ,所以 ,并且 。被检验的除数是 ,其个数为 。如果不存在因子,这些检验每一个都会被执行。
快速检查
(函数 在时间 内被计算,语言 在长度为 的输入上于时间 内被判定。请给出判定 的一个多项式界限,并说明其次数与首项系数。)
解答 · 答案
输出长度至多为 ,所以第二阶段至多需要 步,再加上多项式的转移代价 ,就给出一个多项式界限。该界限的次数为 ,首项系数为 ,因为转移项的次数更低。
快速检查
(长度至多为 的二进制字符串的集合中包含多少个不同的语言?一般地,长度至多为 的二进制字符串的集合中包含多少个?)
解答 · 答案
长度至多为 的二进制字符串有 个(空字符串、两个长度为一的、四个长度为二的),而每个语言都是这些字符串的一个子集,所以共有 个语言。一般地,长度至多为 的字符串有 个,因此语言有 个。
续篇《归约、识别器与有界时间对角化》继续讨论归约和后面的对角构造。