计算复杂性理论（八）

但请注意，这类理论家通常会小心避免明确断言可行数只有有限个。相反，他们给出一些表达式的例子，这些表达式的含义（如果它们存在的话）会大到不可行，例如 (S2) 公式中给出的含义。当然，声称存在最大的可构造数会引发严格有限主义者提名这样一个数字 n 的挑战。而任何这样的提名反过来又会引发这样的反驳：如果 n 是可构造的，那么 n+1 也必须是可构造的。但是在所考虑的模型M中，明确描述“存在最大的x，使得2x”将是非指示性的，因为元素n∈M，使得M⊨∃zε(2,n,z)形成适当的初始段。因此，此类模型的存在可能被用来阐明Yessenin-Volpin (1970)的主张，即存在不同的自然数序列，它们由原始递归函数来区分，在这些原始递归函数下它们是封闭的。[55]

4.7 逻辑知识和演绎推理的复杂性

迄今为止讨论过的复杂性理论和认识论之间最直接的联系是由以下观察结果所介导的：确定逻辑有效性（和相关属性）通常是一项计算困难的任务。一方面，认识论中的传统观点是逻辑知识——例如，某些陈述是逻辑有效性的知识——是先验知识的典型例子。如果这是正确的，那么我们似乎应该相信正常的认识论主体具有对命题逻辑和一阶逻辑等系统的逻辑有效句子类的知识，这些系统通常被认为是日常推理的基础。但另一方面，第 4.2 节中给出的结果清楚地表明，确定 ϕ 是否是这些系统之一的有效性的问题在计算上是难以解决的。

一方面，哲学观点认为逻辑有效性应该很容易知晓（例如，由于它们不需要经验证实），另一方面，即使最弱的熟悉系统的有效性和可满足性问题也难以解决，这种明显的冲突导致了传统上认识论者感兴趣的两个发展：逻辑全知问题和最小或有限理性理论研究。

逻辑全知问题通常被认为起源于被称为认识论逻辑的学科。在这种情况下，知识被视为模态算子 Ki，其中形式为 Kiϕ 的句子被分配了预期的解释代理 i 知道 ϕ。目标是制定公理和规则，以描述我们应该如何推理这种形式的陈述。例如，对陈述的知识蕴含其真实性的原理被表示为 Kiϕ→ϕ ，而对合取词的知识蕴含对其合取词的知识的原理被表示为 Ki(ϕ∧ψ)→(Kiϕ∧Kiψ)。其他原理——例如 ¬Kiϕ→Ki¬Kiϕ，表示 i 不知道 ϕ 蕴含着他知道这种不知道——被认为更具争议性。然而，一致的观点（例如， Hintikka 1962； Lenzen 1978； Fagin 等人 1995）是，最可辩护的知识逻辑选择位于模态系统 S4 和 S5 之间。

尽管对 Ki 采用了精确的公理化，但使用模态逻辑来模拟知识推理会产生以下两个结果：

对于所有 ϕ∈VALID Kiϕ

如果 Γ⊨ϕ 且 Kiψ 对于所有 ψ∈Γ，则 Kiϕ

(i) 和 (ii) 分别报告称，代理的知识包括所有命题重言式，并且他所知道的句子集在逻辑结果下是封闭的。[56] 然而请注意，相对于我们对知识的日常理解，这两个结果似乎表面上难以置信。因为一方面，不仅存在无限多不同的命题重言式，而且甚至还有相对较短的命题重言式，许多正常的认知代理无法识别它们。另一方面，人们普遍承认，我们所知道或相信的句子集（至少在明确的意义上）在逻辑结果下不是封闭的。这通常可以通过观察来说明：一个原本有能力的认知主体可能知道一个数学理论（例如 PA）的公理，但不知道它的所有定理（例如素数的无穷大）。

第 4.2 和 4.3 节中总结的结果强调了这些问题的严重性。首先请注意，判断给定公式是否为重言式的问题是 coNP 完全的，因此很可能难以解决。但我们也看到，证明复杂性的结果强烈表明，主体可能采用的任何用于推理命题逻辑（例如自然演绎）的证明系统都将是这样的：有无数个陈述，它们的最简单证明的长度至少是其大小的指数级。因此，很可能存在“短”重言式——例如少于 100 个命题字母——在传统的自然演绎系统中，它们的最短证明将长得像天文数字。类似的说法也适用于确定一组有限的句子 {ψ1,…,ψn} 是否一致的问题——这项任务在日常推理中肯定具有认识论意义。特别是，很容易看出，一致性检查只是对典型 NP 完全问题 SAT 的重新描述。

Cobham-Edmonds 论题（以及对开放问题 1 和 2 的预期肯定回答）已经得出这样的结论：这类问题在计算上是难以解决的。但如果我们放弃日常推理基于经典命题逻辑的简化假设，那么有效性和一致性检查只会变得更加困难。例如，如果我们认为代理可以使用诸如 S4 或 S52 之类的模态逻辑推理他们自己的知识或他人的知识，那么相应的有效性和可满足性问题就变为 PSPACE 完全的。如果我们假设它们以命题相关逻辑、经典一阶逻辑或直觉一阶逻辑进行推理，那么有效性问题就变得 RE-complete（即和停机问题一样难）。

对这些观察的一个常见反应是承认，尽管传统认识论逻辑的公理看似合理，但它们形式化的不是我们对知识的日常理解，而是一个理想化或“隐含”的概念，更接近“原则上的可知性”（例如 Levesque 1984；Stalnaker 1991；1999）。另一种反应是试图修改认识论逻辑语言的解释，以减轻 (i) 和 (ii) 的影响。这可以通过改变所讨论的模态语言的语义有效性来实现 - 例如通过使用所谓的不可能世界（Rantala 1982）、意识模型（Fagin and Halpern 1988）或局部模型（Fagin and Halpern 1988）。但是，尽管这些技术可用于规避（i）和（ii）的特殊情况，但它们通常也会使解释为什么代理所知道的句子集可能表现出一些潜在的理想闭包属性（例如，对合取词的知识意味着对其合取词的知识）的任务复杂化。

Artemov 和 Kuznets (2014) 提出了一种明确考虑计算复杂性的逻辑全知方法。他们认为，知识逻辑不仅应该形式化“φ 可被代理 i 所知”形式的陈述，还应该形式化“φ 可被代理 i 根据证据 t 所知”形式的陈述。然后，他们展示了一组用于推理后一种形式的陈述的论证逻辑，这些陈述满足所谓的强逻辑全知测试——即，如果形式为“代理 i 根据证据 t 知道 ϕ”的陈述是可推导的，则可以在大小为 t 和 ϕ 的时间多项式中找到 ϕ 的证明。

上述对认识论逻辑的修改大体上属于被称为有限理性的学科范围——例如，参见（Simon 1957；Simon 1972；Rubinstein 1998；Gigerenzer 和 Selten 2002；Kahneman 2003）。这一发展可以追溯到决策理论和认知心理学的研究，这些研究试图考虑到人类主体在日常决策中面临资源限制。开发考虑资源限制的决策模型的尝试有时被视为与经济学和政治学中经常使用的理性选择的规范模型的对立面。在这种情况下，决策通常被建模为一种优化形式。特别是，传统上要求完全理性的主体能够在一系列替代方案中找到最佳选择，尽管在这些替代方案中进行搜索可能不可行。

这些发展是认识论争论的背景部分，这一争论源于切尔尼亚克 (1981; 1984; 1986) 的最小理性理论。切尔尼亚克试图提供一种理性特征，它既能响应传统的规范性特征，也能响应复杂性理论关于上述演绎推理难度的结果。根据他的解释，一个最小理性的主体只需要根据他在经典逻辑证明系统中的信念做出一些有效的推论。他进一步指出，所选择的推论可能取决于认知心理学家如特沃斯基和卡尼曼 (1974) 所考虑的启发式类型。因此，切尔尼亚克提出，在某些情况下（即使是可能不健全的情况下），启发式方法的使用可能对主体有益，应该被视为属于计算复杂性理论所形成的广义理性描述。 Harman (1986) 和 Morton (2004; 2012) 讨论了相关主题。

5. 进一步阅读

西方和苏联学派早期计算复杂性理论发展的历史调查分别见 (Fortnow and Homer 2003) 和 (Trakhtenbrot 1984)。 (Wagner and Wechsung 1986) 和 (Emde Boas 1990) 详细介绍了机器模型、模拟结果、不变性论题的状态以及第一和第二机器类之间的区别。 (Allender and McCartin 2000)、(Harel 2006)、(Cook 2012) 和 (Fortnow 2013) 以半通俗形式介绍了复杂性理论的基本主题。在许多关于理论计算机科学的本科普通教科书中也可以找到介绍性的内容，例如 (Hopcroft and Ulman 1979)、 (Lewis and Papadimitriou 1998) 和 (Sipser 2006)。关于复杂性理论的更高级的教科书包括 (Papadimitriou 1994)、 (Du and Ko 2000)、 (Hemaspaandra and Ogihara 2002)、 (Arora and Barak 2009) 和 (Goldreich 2010)。其中许多书籍涵盖了本文未涉及但可能引起哲学家兴趣的主题，例如随机算法、概率可检查证明、自然证明、零知识证明和交互式证明系统。 (Van Leeuwen 1990) 包含有关几个复杂性相关主题的综述文章。关于 NP 完全性的标准参考文献（Garey and Johnson 1979）仍然存在，其中包含 300 多个 NP 完全问题。关于 P 完全性的类似参考文献是（Greenlaw、Hoover 和 Ruzzo 1995）。结构复杂性理论——即对不同归约概念和相应程度结构的研究——由（Balcázar、Diaz 和 Gabarró 1988）和（Odifreddi 1999）发展而成。教科书分别由（Cook and Nguyen 2010）、（Immerman 1999）和（Hájek and Pudlák 1998）提供了对证明复杂性、描述复杂性和有界算术的处理。 （Moore 和 Mertens 2011）和（Aaronson 2013b）也提供了最近的哲学导向的复杂性理论调查。

%00