计算复杂性理论（七）

Cobham (1965) 对 FP 的原始表征提供了形式算术和复杂性之间的第一个联系，其术语为类似于定义原始递归函数的函数代数。所讨论的类由以下基函数类 F0 生成：

z(x)=0,s0(x)=2⋅x,s1(x)=2x+1,πin(x1,…,xn)=xi,x#y=2|x|⋅|y|

我们还定义了以下原始递归变体：

定义 4.1 函数 f(→x,y) 被称为从 g(→x)、h0(→x,y,z)、h1(→x,y,z) 和 k(→x,y) 通过符号上的有限递归定义，只要

f(→x,0)=g(→x)f(→x,s0(y))=h0(→x,y,f(→x,y))f(→x,s1(y))=h1(→x,y,f(→x,y))

并且对于所有 →x,y，f(→x,y)≤k(→x,y)。

我们将符号上的有限递归可定义的函数类 F 定义为包含 F0 的最小类，并且在组合和前述方案下封闭。 Cobham 原始结果的一个略微变体现在可以表述如下：

定理 4.4（Cobham 1965；Rose 1984）当且仅当 f（→x）∈F 时，f（→x）∈FP。

与定理 4.2 和 4.3 一样，定理 4.4 很重要，因为它提供了另一个与机器无关的重要复杂性类的特征。然而，回想一下，Cobham 工作的时候，可行性概念的数学地位仍在争论中。因此，也有理由问，F 的定义是否可以理解为提供独立动机的可行可计算性分析，类似于 Church 和 Turing 经常被认为提供的有效可计算性的分析。

相对于第 1.1 节中讨论的标准，似乎有理由坚持认为基函数 F0 是可行可计算的，并且该属性在组合下得以保留。现在假设 f(x,y) 由 g(x)、h0(x,y,z)、h1(x,y,z) 和 k(x,y) 通过有限递归符号定义。在这种情况下， f(x,y)=hi(x,⌈y2⌉,f(x,⌈y2⌉)) 取决于 y＞0 是偶数（i=0）还是奇数（i=1）。由此可知，计算 f(x,y) 值所需的递归深度将与 log2(y) 成正比 - 即与 y 二进制表示的长度成正比，而不是与 y 本身成正比，就像 f(x,y+1) 通过普通原始递归定义为 h(x,y,f(x,y)) 一样。这表明，当函数由有限递归符号定义时，可行性也得以保留。

仅从理论前的角度很难解释在 F0 中包含函数 xy：以及在定义 4.1 中包含条件 f(x,y)≤k(x,y)。因为 F 定义的这些特征可以准确地看出对辅助函数设置了多项式界限，这些辅助函数可以在刚才描述的长度有界递归期间计算出来。另一方面，由于 Leivant (1994)（使用一种对字符串的正二阶可定义性形式）和 Bellantoni 和 Cook (1992)（使用传统原始递归方案的结构修改），在类似的 FP 函数表征中避免了对多项式增长率的这种间接引用。

在现称为 IΔ0 的一阶算术理论（最初由 Parikh (1971) 以 PB 的名称引入）的表述中，也避免直接引用多项式增长率。IΔ0 采用传统的一阶算术语言（即 La={0,s,+,x,＜}）表述，由 Robinson 的 Q 公理以及 PA 算术的归纳方案对 Δ0 公式的限制组成，即仅包含形式为 ∀x≤t 或 ∃x≤t 的有界量词，其中 t 是不包含 x 的项。

在此之前，Bennett (1962) 已经证明存在一个 Δ0 公式 ε(x,y,z)，它定义了指数函数相对于标准算术模型的图形。IΔ0 证明 ε(x,y,z) 满足指数的标准定义方程。但也可以证明，该理论不能证明在此定义或任何其他定义下指数的完整性：

定理 4.5 (Parikh 1971) 假设 IΔ0⊢∀→x∃yϕ(→x,y)，其中 ϕ(→x,y) 本身是 Σ1。那么对于某个 La 项 t(→x)，IΔ0⊢∀→x∃y≤t(→x)ϕ(→x,y)。

回想一下，只要存在一个 Σ1 公式 ϕf(→x,y)，用 T 的语言定义 f(→x) 的图，使得 T⊢∀→x∃!yϕf(→x,y)，那么函数 f(→x) 在理论 T 中是可证明完全的。由于算术语言中的项是具有正系数的多项式，因此根据定理 4.3，IΔ0 的所有可证明完全函数都具有多项式增长率。特别是，指数运算在这个理论中不是可证明完全的。因此，Parikh 将 IΔ0 称为“拟人系统”。[47]

为了获得精确描述 P 和 PH 更高级别的算术理论，人们分别采用了 Buss (1986) 和 Zambella (1996) 提出的两种方法。Buss 提出了一系列一阶理论

S12⊆T12⊆S22⊆…Si2⊆Ti2⊆Si+12⊆…

其可证明的总函数对应于层次结构 ◻Pi 的级别。这些理论在语言 Lba={0,s,+,x,＜,|⋅|,⌊x2⌋,}：上表述，其中 |x| 的预期解释为 ⌈log2(x+1)⌉，xy：的预期解释为 2|x|⋅|y|，如上所述。传统有界量词的形式为 ∀x＜t 或 ∃x＜t，而所谓严格有界量​​词的形式为 ∀x＜|t| 或 ∃x＜|t| （其中 t 为不涉及 x 的 Lba 项）。句法类 Σbi 和 Πbi 的定义方式类似于传统算术层次结构中类 Σ0i 和 Π0i 的定义方式，即通过计算有界量词的交替，忽略严格有界的量词。

理论 Si2 和 Ti2 都扩展了称为 BASIC 的基础理论。 BASIC 包含 32 条公理，其中包括 Q 的公理，以及其他将 |…|、⌊x2⌋ 和 # 的预期解释公理化的公理（例如，参见 Hájek 和 Pudlák 1998，321-22）。我们还定义了以下归纳模式：

对于所有 ϕ(x)∈Σbi，Σbi-IND ϕ(0)∧∀x(ϕ(x)→ϕ(x+1))→∀xϕ(x)。

对于所有 ϕ(x)∈Σbi，Σbi-PIND ϕ(0)∧∀x(ϕ(⌊x2⌋)→ϕ(x))→∀xϕ(x)。

最后，我们定义理论 Si2=BASIC+Σbi-PIND 和 Ti2=BASIC+Σbi-IND，以及 S2=⋃i∈NSi2 和 T2=⋃i∈NTi2。

将语言 Lba 和这些理论与多项式层次联系起来的一些基本结果如下：

定理 4.6（Kent 和 Hodgson 1982）集合 X 属于 ΣPi 当且仅当 X 在标准模型中可以通过 Σbi 公式 ϕ(x) 定义 - 即 X={n∈N∣N⊨ϕ(¯n)}。

定理 4.7 (Buss 1986) 函数 f(→x) 属于 ◻Pi 当且仅当 f(→x) 在 Si2 中相对于 Σbi 定义可证明为完全的，即当且仅当存在 Σbi 公式 ϕf(→x,y) 使得 Si2⊢∀→x∃!yϕf(→x,y)。

根据定理 4.7，仅当 f(→x) 在 S12 中相对于 Σb1 定义可证明为完全的时，它才是多项式时间内可计算的。Buss (1986) 还证明了 Si2⊆Ti2⊆Si+12，Si2 和 Ti2 是有限公理化的，并且 S2=T2。目前尚不清楚上述理论层次结构是否会崩溃，也不清楚 S2 或 T2 是否可有限公理化。但是，可以证明存在 i 使得 Ti2=Si+12，或者 S2 或 T2 可有限公理化，都会导致多项式层次结构的崩溃。

将形式算术与 PH 联系起来的第二种方法采用了一系列二阶理论 V0⊆V1⊆…，最初由 Zambella (1996) 引入（另见 Cook 和 Kolokolova (2001) 以及 Cook 和 Nguyen 2010）。它们扩展了一阶语言 La，符号为 ∈ 和 |⋅|以及用于范围在有限自然数集上的量词 ∀X 和 ∃X。理论 V1 使用二阶量词公理、集合的外延性、形式化为 |X| 表示 X 的最大元素的公理以及 ΣB1 公式的二阶理解模式扩展了 Q——即仅包含有界一阶量词和形式为 ∃X(|X|≤t) 的集合量词（其中 t 是不包含 X 的一阶项）的公式。与定理 4.7 并行，可以证明，仅当函数 f(→x) 可以通过 ΣB1 公式定义并且相对于该公式在 V1 中可证明是完全的，它才在 FP 中。通过将理解扩展到更广泛的有界二阶公式类，可以通过考虑理论 Vi（对于 i＞1）来获得对类 ◻Pi 的类似表征。

4.6 严格有限主义

迄今为止，数学哲学与计算复杂性理论之间最直接的联系出现在传统上称为严格有限主义的观点的讨论背景下。这种观点与 Yessenin-Volpin (1961; 1970) 最为相关，他最出名的是质疑诸如 1012 或 250 之类的表达式是否表示自然数。假设这些表达式表示，Yessenin-Volpin 认为它们不能用来描述他所说的可行数字 - 即我们在实践中可以计算的数字。在此基础上，他概述了一个基础纲领，其中可行性被视为基本概念，并质疑支持数学归纳法有效性和自然数系列唯一性的传统论据。这种观点的前身可以在（例如）伯内斯（1935 年）、范丹齐格（1955 年）和王（1958 年）的作品中找到。[48]

回想一下，与希尔伯特纲领相关的传统有限主义形式的一个原则是，自然数不应被视为包含一个完整的无限总体。严格的有限主义者有时被描述为比这更进一步，并积极否认有无限多个自然数。然而，以下更能体现这些理论家明确认可的主张：

（S1）可以识别一类自然数，它们对应于那些可以通过计数在实践中构造的自然数，或者其值可以具体或直观地明确表示为数字的自然数。

(S2)我们拥有一些符号，例如十进制数字 101010、67257729、1012，它们不表示此类中的数字。

在强调我们在执行算术计算过程中如何使用数字来表示自然数的实际方面时，很明显，激发严格有限主义的关注点预见了复杂性理论发展的一些关注点。尽管如此，严格有限主义的追随者并不多。要了解原因，请观察 (S1) 明确指出，严格有限主义者建议将自然数与数字（例如熟悉的一元数字序列 0,0′,0″,...）联系起来。

如果我们将此类表达式视为标记而不是类型，那么通过按照 Yessenin-Volpin 描述的意义构造数字的一元表示来具体考虑“计数到”数字的任务是有意义的。回想一下，数字的一个特征是，它们可以通过应用一组有限的句法形成规则从某些初始符号生成——例如，一元数字是通过将形成规则 σ↦σ′ 应用于初始符号 0 而生成的。但一旦承认这一点，似乎也很难抗拒以下附加论点：

(S3) 如果数字 σ 可以可行地构造，那么 σ′ 也可以（即表示 σ 所表示数字的后继的一元数字）。[49]

在试图同时容纳 (S1)-(S3) 时，我们必须面对一种张力，这种张力导致许多作者跟随 Dummett (1975) 得出严格有限主义缺乏连贯表述的结论。假设我们让 F(x) 表示 x 表示 Yessenin-Volpin 意义上的可行数字。那么，从 (S1) 可以看出，我们应该接受

F(0)

但从 (S3) 可以看出，我们也应该接受

∀x(F(x)→F(x+1))

从 (S2) 可以看出，我们应该接受

¬F(τ)

其中 τ 是一个表示“不可行数”的表达式，例如 1012、101010 或 67257729。

达米特观察到，经典的 sorites 悖论的两种不同形式现在介入，表明 (i)–(iii) 是不一致的。因为一方面，通过应用数学归纳法（即对于自然数的所有确定属性 P(x)，我们可以从 P(0) 和 ∀x(P(x)→P(x+1)) 推出 ∀xP(x)），到谓词 F(x)，我们可以从 (i) 和 (ii) 得出 ∀xF(x)。但这样一来，F(τ) 就通过全称实例化而来，与 (iii) 相矛盾。另一方面，即使不诉诸归纳法，也可以通过条件堆垛论证的形式得出矛盾，即通过将 F(τ) 反复应用于通过全称实例化从 (ii) 获得的系列 F(0)、F(0)→F(0′)、F(0′)→F(0″)、… 的结果来推导出 F(τ)。

虽然认为 Yessenin-Volpin 不知道这些观察结果会有些不厚道，但第一个直接回应 (S1)-(S3) 不一致指控的人似乎是 Parikh (1971)。[50] 他的回应可以理解为由两部分组成，两部分都与第 1.1 节和 2.2 节中考虑的可行性的非正式概念的分析有关。一方面，Parikh 考虑了他所说的几乎一致理论 PAF。该理论在语言 La∪{F(x)} 上表述，并补​​充了所有封闭原始递归函数的项，并包含语句 ¬F(τ)，其中 τ 是某个固定的原始递归项，旨在表示一个“不可行”的数字，例如 1012。最后，PAF 包含 PA 的公理，其归纳模式仅限于不包含 F(x) 的公式。

鉴于后一个限制，在 PAF 中模仿 sorites 论证的归纳形式是不可能的。但当然，由于论证的条件形式，PAF 仍然是不一致的。尽管如此，Parikh 表明，对于适当的 τ 选择，PAF 中任何矛盾的证明本身都必须非常长。例如，如果我们考虑超指数函数 2⇑0=1 和 2⇑(x+1)=22⇑x，并让 τ 成为本原递归项 2⇑2k，那么根据 Parikh 的结果，PAF 中任何矛盾的证明都必须大约 2k 步长。例如，如果 τ=2⇑21000，那么这样的证明必须至少有 21000 行长。[51]这表明，严格有限主义者有可能对达米特反对严格有限主义的论证做出两部分的回应：[52]

由于 F(x) 不是自然数的确定（即非模糊）属性，因此排除了 sorites 的归纳形式。

至少对于 τ 的某些选择，条件形式也不构成威胁，因为从 (i)-(iii) 得出矛盾的唯一推导太长，无法在实践中进行。

尽管存在这样的答复可能性，但此时我们也很自然地会问，复杂性理论中考虑的可行性概念是否也可能模糊，从而可能使其容易受到达米特 (1975) 设想的那种 soritical 论证的影响。但请注意，我们迄今为止的讨论表明，严格有限主义者感兴趣的可行性概念是单个自然数的属性。这与我们在复杂性理论中看到的处理这一概念的方式不一致。例如，为了运用科巴姆-埃德蒙命题来判断问题 X 是否可行，我们考虑决定 X 的最有效算法的时间复杂度 t(n) 的增长阶。从复杂性理论的角度来看，可行性是一个不适用于单个自然数 n 的概念，而是适用于 N→N 类型的时间复杂度函数或其增长率。

接下来观察以下是科巴姆-埃德蒙命题的结果：

O(1)（即常数时间）是可行的增长率。

由于所有多项式增长阶都是可行的，因此如果 O(nk) 是可行的，那么 O(nk+1) 也是可行的。

超多项式增长阶如 O(2n) 是不可行的。

基于此，人们可能确实担心，由 Cobham-Edmonds 论题编纂的关于可行可计算函数的直觉表现出与直观上可接受的可行可构造数原理相同的不稳定性。

然而，要看到情况并非如此，请观察我们比较 f,g:N→N 的增长率，不是按照自然数的标准排序 ＜ ，而是按照以下排序 ≺：

O(f(n))≺O(g(n)) 当且仅当存在 n0,c∈N 使得对于所有 n＞n0,f(n)＜c⋅g(n)

此定义的结果是 O(1)≺O(n)≺O(n2)≺O(n3)… ——即多项式增长阶确实形成关于 ≺ 的 ω 序列。然而，由此还可知，对于所有 k∈N，O(nk)≺O(2n)——即，O(2n) 是相对于该排序位于每个多项式增长阶之上的“无穷远点”（所有其他超多项式增长率也是如此）。[53] 由此可知，此类排序不能通过类似出击的可行增长阶序列从下方达到，O(1)≺O(n)≺O(n2)≺O(n3)……根据科巴姆-埃德蒙兹论文进行分析，因此，可行可计算性的“朴素”概念似乎不会受到杜米特所认为的可行可构造数概念所遭受的那种不稳定性的影响。

这些观察结果指向了一些严格有限主义者著作中的另一个主题，即他们也预见了诸如“可行”和“不可行”等谓词现在在复杂性理论中的使用方式。例如，虽然范丹齐格（1955）认为可行数在加法和乘法下是封闭的，但耶塞宁-沃尔平（1970）明确指出，它们不应被视为在指数运算下封闭。耶塞宁-沃尔平和其他人提出的“不可行数”的具体例子通常采用指数或迭代指数符号，形式为 nn21 或 nnn321，这也表明指数运算应该被理解为在严格有限主义本身的表述中发挥作用。这反过来又提出了对基于出击的反对严格有限主义论点的另一种回应。

回想一下，第 4.5 节中介绍的理论 IΔ0 使我们能够通过 Δ0 公式 ε(x,y,z) 定义指数函数 xy 的图形，即 IΔ0⊢∀xε(x,0,1) 和 IΔ0⊢∀x∀y∀z(ε(x,y,z)→ε(x,y+1,z⋅x))。但正如我们所见，IΔ0 并不能证明指数函数的全部，Buss 的理论 S12 也不能证明（也可以证明）。由此可知，理论 S12+∃y¬∃zε(2,y,z) 在证明理论上是一致的。根据一阶逻辑的完备性定理，存在一个有界算术语言模型 M，使得 M⊨S12+∃y¬∃zε(2,y,z)。但是，尽管根据定理 4.5 可以得出，所有多项式时间可计算函数对于 M 中的所有输入都是定义的，但在 M 的定义域中也存在一个对象 a，满足 ¬∃zε(2,a,z)。由此可知，我们通常写为“2a”的表达式不能表示 M 中的值。[54]

当然，任何模型 M⊨S12+∃y¬∃zε(2,y,z) 都必须是非标准的。因此，不仅 M 的定义域必须是无限的，而且存在 M 意义上的“自然数”，从 M 外部看，它们有无数个前身。因此，人们一开始可能会认为，使用像 M 这样的结构来探索严格有限主义的后果会与其支持者的观点相悖。