跳至正文

P vs NP 的哲学外推大体检

目录

「创造比验证难，所以创造力不可能被自动化」「P≠NP 证明了人类的特殊」「机器永远成不了莫扎特」——本篇把「P≠NP」这门招牌拉上被告席。它比哥德尔定理更险：哥德尔定理是已证的，而 P≠NP 连证明都没有（William Gasarch 三次民调相信 P≠NP 的比例 61%→83%→88%、专家 99%，却零证明），偏偏被当成「已确立的自然定律」给人类创造力上保险。沿硬度递减、宏大递增的五层光谱：① 已证硬骨（Cook-Levin 定理、NP 完全性理论、证明障碍三件套）硬到是定理——但只说形式系统内的可归约性，不直接说现实任何东西难；② 条件性硬结果（「若 P≠NP 则……」）是定理但前件未证；③ P≠NP 猜想本身是 88% 的信念、零证明，障碍三件套恰恰证明「我们现有的所有证明技术都证不出它」；④ 现实可计算性主张（「NP 难问题现实不可解」）双向证伪——SAT solver 日解千万变量、galactic algorithm n^(2^100) 名义多项式却永不可算；⑤ 创造力护城河（「创造比验证难＝创造力不可自动化」）是连命题都不是的口号。脊柱不是公式，是「P≠NP」这个名号沿两条正交方向滑动：认识论上从「未证猜想」滑成「已知定律」，语义上从「最坏情况算法不存在」滑成「人类创造力的形而上护城河」——而把这两道偷换焊成一句口号的，是 Scott Aaronson「能欣赏交响乐的人都成了莫扎特」那句被作者本人加了 caveat 的修辞，被当成了字面定理。最强一刀对称——这场关于创造力的争论，神化派与反神化派共押了一座从未架起的桥：「人类创造力 ≡ 求解某类 NP 难问题」。无论 P 是否等于 NP，这场争论在被回答之前就已经脱靶。

〇 母裁决·五层硬度光谱

把「P vs NP」一刀切开，会看到五层在硬度上递减、在宏大上递增的不同东西。滥用者的全部修辞，是借第一层（已证定理）的硬度，卖第五层（形而上口号）的宏大——这条「硬度走私通道」就是本篇要逐层堵死的。

层 在说什么 认识论地位 软在哪类诉求
① 已证硬骨·最硬 Cook-Levin（SAT 是 NP 完全）＋Karp 21 问题＋NP 完全性理论（数千问题精确等价）＋证明障碍三件套＋Williams NEXP⊄ACC⁰ 定理，已证 本体诉求：关于形式系统内可归约性的定理，不直接说现实世界任何东西难——「SAT 是 NP 完全」不等于「你手上的 SAT 实例难」。
② 条件性硬结果 「若 P≠NP 则 NP 完全问题无多项式算法」「单向函数存在 ⟹ P≠NP」、密码学的条件安全归约 定理，但前件未证 逻辑诉求：全是 if-then，前件本身未证；把条件式当无条件结论，是第一道滑。
③ P≠NP 猜想本身 P≠NP（渐近最坏情况下 NP ⊄ P） 猜想。88% 信、专家 99% 信，零证明 认识论诉求：「共识」是社会学事实不是数学事实；障碍三件套恰恰证明了我们为什么没有证明。这是脊柱的支点。
④ 现实可计算性主张 「NP 难问题在现实中算不动」「P≠NP 保护了密码学」 经验主张，双向证伪 统计/经验诉求：最坏情况⊥平均情况⊥真实实例；SAT solver 与 galactic algorithm 双向打脸；密码学还需单向函数存在（可能落在 Pessiland）。
⑤ 创造力护城河·最软最宏大 「P≠NP 给创造力上了数学保险」「创造比验证难＝创造力不可自动化」「AI 永远成不了莫扎特」 口号。无形式化、无证明、连命题都不是 认知/形而上诉求：把复杂度类之间的关系外推成人脑 vs 机器的本体差异；预设「创造力≡解某类 NP 难问题」这座从未架起的桥。

层间范畴切换：从①到⑤连续切换五种诉求——①是本体（一个归约关系成不成立）、②是逻辑（一个条件命题）、③是认识论（一个命题我们知不知道其真值）、④是经验（现实实例算不算得动）、⑤是认知/形而上（人脑有没有机器没有的能力）。把它们混成一句「P≠NP 证明创造力不可自动化」，就同时在五个法庭越级。[理论整合] [我们的断言]

与哥德尔篇、熵篇的结构差异（写进母裁决的诚实命门）：哥德尔不完备定理、热力学熵都是已证的，那两篇的最硬层是定理。本篇不同——最硬层是 Cook-Levin 与障碍三件套这些「周边已证结果」，而招牌主角 P≠NP 本身停在第③层猜想。第③层是唯一一层「宏大、但你其实希望它软（它确实只是猜想）」。这道结构胎记贯穿全篇：凡把 P≠NP 当「已知」用的，第一步就踩空了。[我们的断言]

一、承重墙·八柱：NP 不是「非多项式」

P vs NP 是全库门槛最高的主题，外推几乎全部发生在概念混用的缝里。先把八根柱子钉死——尤其第一柱，它是整条语义滑动的病原体。

  1. NP ≠ non-polynomial（去污染弹头·打头）：NP 是 nondeterministic polynomial（非确定性多项式时间可验证），不是「non-polynomial＝非多项式＝超级难」。P ⊆ NP，NP 里装满了「易」问题（凡多项式可解的都在 NP）。一旦读者望文生义把「NP」读成「难到非多项式」，后面「难→创造力护城河」就毫无阻力——所以这一柱必须第一句钉死。[文献较稳]
  2. 真问题是 verify ⟹ solve? 不是「有多难」：P vs NP 问的是「凡能在多项式时间验证答案的问题，能否也在多项式时间求解」，是一个结构问题，不是「世界有多难」的程度感叹。
  3. 最坏情况 vs 平均情况 vs 真实实例：复杂度类按渐近最坏情况定义。三种难度互不蕴含——一个问题可以最坏情况 NP 完全、却在你关心的实例上秒解（命门二的承重墙）。
  4. NP-complete vs NP-hard vs NP：不是所有 NP 问题都 NP 完全（若 P≠NP，Ladner 定理保证存在「中间」问题）；NP-hard 可以比 NP 还难、不一定在 NP 里。外推者常把「某问题 NP 难」偷换成「我的任务属于这个最难类」。
  5. 多项式 ≠ 可行（galactic algorithm；Cobham-Edmonds 是论题不是定理）：n^100、甚至 n^(2^100) 名义上是「多项式」，却永远算不动；2^(0.00001n) 名义上是「指数」，在 n＝百万时也只是 2^10、轻松可解。「多项式＝可行」（Cobham-Edmonds 论题）是一个约定/论题、不是定理。
  6. 判定 vs 搜索 vs 优化：P vs NP 严格说是判定问题（yes/no）之间的问题；「创造」就算沾边也更像搜索/优化——这层在自指落点要用到。
  7. solve vs verify vs appreciate（三联）：NP 的「verify」是给定一份证书、做多项式时间检查；人类「鉴赏一首交响乐」没有这样一份可检证书。把后者当前者，是哲学外推的核心偷换（命门四）。
  8. 复杂度 vs 可计算性（接哥德尔篇）：复杂度是资源有界的可行性，可计算性是原则上的可能性；停机问题/哥德尔不完备关的是可计算性，P vs NP 关的是复杂度——哥德尔不完备滥用篇已明言两者「正交但是姊妹」，本篇正面接住那条让位。[多源交叉]

柱 1、5、7 是本篇三根真承重墙；其余五根是防串味的隔断。

二、脊柱·一个名号，两道滑动

EMH 篇的脊柱是「市场有效」在五义间滑动，哥德尔篇的脊柱是「哥德尔析取」被偷塌成一支。P vs NP 的病更复杂——它有两道独立的偷换，所以脊柱不是一条单调阶梯，而是一个名号 + 两条正交滑动的十字。

轴 M（模态/认识论滑动）——「P≠NP 的认识论地位」：

  • M1 未证猜想（88% 信、专家 99% 信，但零证明；障碍三件套证明「现有所有证明技术都证不出它」）
  • M2 社会学共识（「专家都信」被悄悄偷换成「已确立」）
  • M3 已知定律（「P≠NP 已是事实」——口号层，数学上是错的，它仍是 Clay 悬赏一百万美元的 open problem）

轴 S（语义/外延滑动）——「难在哪、难给谁」：

  • S1 算法不存在性（最坏情况渐近：不存在多项式时间算法解所有 SAT 实例）
  • S2 现实不可解（实际算不动；此层双向打脸——SAT solver 日解千万变量 vs galactic algorithm n^(2^100) 名义多项式却永不可算）
  • S3 求解本质难于验证（solve ≫ verify；Aaronson「creative leaps 有特殊价值」；但 NP 的 verify 是查证书、不是审美）
  • S4 创造力不可自动化（跨出复杂度，进入认知/形而上）

口号层 = M3 × S4 的乘积：「P≠NP（已是定律）证明了人类创造力（一般地）不可被机器替代」。滥用者站在这个右下角，却以为自己站在 M1×S1 的左上角（已证的硬结果）。

脊柱锚点＝Scott Aaronson 2006 年博客「Reasons to believe」里那段被无数次引用的金句（本人 curl 原始 HTML 亲核，它是 Aaronson 列的「相信 P≠NP 的十条理由」中的第 9 条，标签逐字为「The Philosophical Argument」）：

The Philosophical Argument. If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.

关键——和哥德尔本人「只敢把定理说成 only as a disjunction」完全同构：Aaronson 本人在同帖评论区（Comment #6，2006-09-05）就给这段加了 caveat，把它的射程主动收窄（本人亲核）：

It’s as rich as any sort of creativity the fruits of which can be rapidly checked by computer. That includes not only proving theorems (the usual example), but also coming up with succinct models or theories to explain one’s observations. I agree that Mozart is a tougher sell than Gauss and Buffett.

Aaronson 的这句 caveat，就是本篇的「only as a disjunction」：金句的作者清楚地知道它只覆盖「成果能被计算机快速检验的创造力」、还自承「莫扎特比高斯/巴菲特更难自圆其说」；是引用者把一句带条件的修辞当成了无条件的定理。Aaronson 自己甚至把它放在一个达尔文式问句里（亲核原文，注意是「universe we inhabited」过去式）：

if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P≠NP, but for NP-complete problems not being efficiently solvable in the physical world.)

核心断裂句（四刀）：

未证 ≠ 已成定律（M 轴）；最坏情况 ≠ 现实难度（S1→S2）；求解-验证不对称 ≠ 创造-鉴赏不对称（S2→S3，真正的语义偷换）；某些问题难 ≠ 创造力不可自动化（S3→S4）。四刀叠加，就是把一个「还没证明的、关于最坏情况算法的猜想」，当成了「已经证明的、关于人类灵魂的定律」。

第三刀里还埋着一个方向反转的陷阱：NP 的不对称是「验证易、求解难」；而日常直觉「创造比鉴赏难」被偷换成「印证了 solve≫verify」。可是「鉴赏一首交响乐」根本不是「验证一个 SAT 证书」——没有谁给你一份「这是好交响乐」的多项式可检证书。这个「verify」概念的偷换（形式的查证书 → 人类的审美判断）在数学定义内部就崩了，根本不必动用形而上。[我们的断言]

三、命门一·认识论：88% 不是证明

第一道命门问的是 modal 问题：P≠NP 的真值，我们到底知不知道？ 答案是不知道——而且我们知道自己为什么不知道。

信念不是证明。William Gasarch 三次对理论计算机科学界的民调（本人 pdftotext 亲核第三次原文 PDF）：相信 P≠NP 的比例，2002 年发表的第一次是 61%（100 人）、2012 年第二次 83%（152 人，注意维基记 151 是小误、Gasarch 原文与博客都写 152）、2019 年第三次 88%（109/124 人）。专家口径更高——亲核 poll3.pdf 行 1043 逐字：

The Experts: 99% NO, 1% YES.

但 Gasarch 自己就提醒：信念的上升与证明的进展脱节。亲核 poll3.pdf 行 202 逐字（这里 66% 指「认为 P=?NP 会在 2100 年前被解决」的比例）：

In 2019 it is up to 66% which amazes me because, since 2012, there has been little (no?) progress on resolving P=?NP.

换句话说，「88% 的专家相信」是一个关于这个时代主观意见的社会学事实，不是 P≠NP 的数学证据。同一份民调里，认为它「永远不会被解决」的人，比例反而从 5%（2002）、3%（2012）升到 9%（2019）。[多源交叉]

障碍三件套：我们为什么证不出（这是本命门最硬的部分——三个已证的元定理，各自证明「一整类证明技术注定失败」）：

  • 相对化障碍（Baker-Gill-Solovay 1975, SIAM J. Comput. 4(4):431–442）：可以构造一个 oracle A 使 P^A=NP^A、另一个 oracle B 使 P^B≠NP^B。任何「会相对化」的技术（对角线法等）对带 oracle 的世界给出与原世界相同的结论，可两个世界答案相反，故定不了 P vs NP。Aaronson-Wigderson 论文里有一句最干净的复述（本人 pdftotext 亲核 alg.pdf 行 51）：

Therefore any solution to the P versus NP problem will require non-relativizing techniques.

  • 自然证明障碍（Razborov-Rudich 1994 STOC / 1997 JCSS 55(1):24–35）：1980 年代成功的电路下界方法都在找一个「自然性质」（constructive＋large＋useful）。Razborov-Rudich 证明，这类方法若能证出 P≠NP 级别的下界，就能反过来攻破伪随机生成器/单向函数——与密码学界广泛相信的硬度假设矛盾（原文逐字）：

We show that any large and constructive Cn that is useful against P/poly provides a statistical test that can be used to break any polynomial-time pseudo-random number generator.

注意这道障碍限定在非一致/电路（P/poly）设定。

  • 代数化障碍（Aaronson-Wigderson 2008 STOC pp.731–740 / 2009 ACM TOCT 1(1)，本人 pdftotext 亲核全文）：用算术化（arithmetization）逃过相对化障碍的那些非相对化结果（IP=PSPACE 等），其实满足一个更精细的「代数相对化」性质，仍不足以解 P vs NP（亲核 alg.pdf 行 20/151）：

any [resolution of the P versus NP problem will] require non-algebrizing techniques.

绕过模板：Ryan Williams 的 NEXP ⊄ ACC⁰（纠错：这篇是 CCC 2011, pp.115–125；不是常被误挂的 STOC 2011；期刊版 JACM 61(1), 2014）是「同时绕开三道障碍」的范本——它组合了多种方法，每一种各避开一个障碍。主结果逐字「NTIME[2^n] does not have non-uniform ACC circuits of polynomial size」，但它远弱于 P≠NP，P vs NP 仍 open。[文献较稳]

至于 Ketan Mulmuley 的几何复杂性理论（GCT）那条「可能要 100 年」的说法——纠错：它不是 Mulmuley 本人的逐字原话，而是 Lance Fortnow 2009 在 CACM 的转述「Mulmuley himself believes it will take about 100 years」，维基把「himself」悄悄删掉、当成 Mulmuley 自述，是以讹传讹。[有争议]

自指注脚：P vs NP 是 arXiv 上民科「证明」最泛滥的题目之一——本次取证中，搜索引擎首页就排着几篇自称「证明了 P≠NP」的预印本，连搜索引擎自己都加注警告「未经同行评审、几乎必有缺陷」。这与哥德尔篇记录的「哥德尔民科」同构：一个连专家都证不出的命题，民间「证明」越多，越说明它的认识论地位是「未决」而非「已知」。[我们的断言]

四、命门二·最坏 vs 现实

第二道命门问的是语义内涵：就算 P≠NP 为真，它说的「难」是哪一种难？ 答案是——渐近最坏情况的难，而这与「现实算不算得动」之间隔着一条经验的鸿沟。

SAT solver：最坏情况 NP 完全，典型实例却惊人地易。布尔可满足性（SAT）是第一个被证 NP 完全的问题，按最坏情况它是「最难的一类」。可现代 CDCL（冲突驱动子句学习）求解器在工业实例上高效得离谱。Ganesh-Vardi《On the Unreasonable Effectiveness of SAT Solvers》（纠错：这是 Roughgarden 编《Beyond the Worst-Case Analysis of Algorithms》Cambridge 2021 的第 25 章，不是常被误挂的 CACM 文章）摘要逐字：

…engineers have designed and implemented conflict-driven clause-learning (CDCL) SAT solving algorithms that can efficiently solve real-world instances with tens of millions of variables and clauses in them. Despite their dramatic impact, SAT solvers remain poorly understood.

这篇文章的中心谜题句，正是命门二的精确表述：

why CDCL SAT solvers are efficient for many classes of large real-world instances while at the same time perform poorly on relatively small randomly-generated or cryptographic instances.

（诚实留痕：标题里的「unreasonable effectiveness」只作题名、正文里并不作为格言出现，不可伪造成一句正文引文。规模口径：百万变量是稳的下界，Vardi 上探至千万级；「典型易、构造难」的标准解释有三支——随机 k-SAT 的相变 phase transition使最难实例只密集在相变点附近、工业实例的结构性、以及 CDCL 引擎本身。SAT Competition 自 2002 年起年年举办，2022 周年赛把二十年的 5355 道历史题拿出来，最强求解器解出约四分之三——这本身就是「典型可解、最坏硬尾仍在」的活体证据。）

galactic algorithm：名义多项式，却永不可算。反方向同样打脸。Richard Lipton 与 Ken Regan 造的词「galactic algorithm」（本人核 Lipton 2010 原帖）逐字：

A galactic algorithm is an algorithm that is wonderful in its asymptotic behavior, but is never used to actual compute anything.

最锋利的例子：一个运行时间为 Θ(n^(2^100)) 的假想 SAT 算法，名义上是多项式时间、按 Cobham-Edmonds 论题该算「可行」、甚至能直接解决 P vs NP——可它「unusable in practice」，永远算不动任何东西。

「多项式＝可行」是论题不是定理。这条把「P」翻译成「易」的 Cobham-Edmonds 论题（Cobham 1965、Edmonds 1965），斯坦福哲学百科明确把它类比 Church 论题、判为「比 Church 论题更不稳固（less well established）」；维基用「asserts（断言）」并特意提醒「Not to be confused with Cobham’s theorem（别和 Cobham 定理混）」。它有真实反例：n^200/n^1000 名义 feasible 却不可算，而 2^(0.00001n) 在 n=10^6 时只是 2^10、轻松可解。[多源交叉]

命门一 vs 命门二划界：命门一问「P≠NP 真不真、我们知不知道」（modal）；命门二问「（假设它真）这个『难』指的是什么」（语义内涵）。两者正交——你可以完全接受 P≠NP 为真，命门二的鸿沟依然张着口。

五、命门三·必要非充分

第三道命门问的是演绎方向：**P≠NP 为真，到底能推出多少被宣称的东西？** 答案是远比宣称的少——它是很多结论的必要条件，却不是充分条件。这里 Russell Impagliazzo 1995 年的「五个世界」（A Personal View of Average-Case Complexity）是最锋利的框架。

五个世界按硬度/密码可能性递增（verbatim 取自 Fortnow 2004 的权威转述与课程讲义；诚实留痕：Impagliazzo 1995 原文 IEEE 付费墙未取，下列是权威转述的逐字、非原文 p.134–147 逐字）：

  • Algorithmica：P=NP（或道德等价），创造性任务有高效算法，几乎无密码学。
  • Heuristica：P≠NP，但 NP 问题平均情况易。
  • Pessiland：NP 问题平均情况难，但不存在单向函数——「最坏的世界」。
  • Minicrypt：单向函数存在，但无公钥密码。
  • Cryptomania：公钥密码可能（如大整数分解平均指数难）。

Pessiland 的逐字（Fortnow）正是命门三的核心：

Pessiland: NP problems are hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. This is the worst of all possible worlds…

箭头不对称（命门三的承重，本人采信 agent 亲核的 AGGM 2005 原文逐字）：

  • 已确立的方向：「存在单向函数 ⟹ P≠NP」。AGGM 逐字「the existence of one-way functions implies that NP is not contained in BPP」（NP⊄BPP 蕴含 P≠NP）——直觉是反演单向函数是个 NP 搜索问题，故有 OWF 就有 P≠NP。这一步容易、已证。
  • 未证的圣杯方向：「P≠NP ⟹ 存在单向函数」。AGGM 把它逐字标为公开问题「A puzzling question of fundamental nature is whether or not the necessary worst-case condition is a sufficient one」——即使 P≠NP（甚至平均情况难），也可能落在 Pessiland、没有单向函数。而且这个方向不只是未证：Brassard 早就指出「反演单向置换的任务不可能在确定性归约下是 NP 难的，除非 NP=coNP」，AGGM 的负面结果进一步把朴素归约路径堵到「coNP ⊆ AM」（广信为假）。

所以承重句是：**人们以为 P≠NP 是密码学（乃至「创造力护城河」）的充分基础，真相是它顶多是必要条件，而通向充分性的那一步——排除 Pessiland——是复杂度密码学至今未解的圣杯。（诚实边界：这不是说反向箭头「已被证伪」，AGGM 自己留了口子「does not rule out」基于 NP∩coNP 等子类、或非黑盒归约；它只是「已知朴素路径走不通、整体仍 open」。当代正用 meta-complexity 一线逐步排除 Pessiland——纠错：「共识是 Pessiland 可被排除，但早晚不知道」这句出自 Quanta 2022 里的 Ryan Williams**，不是 Impagliazzo。）[文献较稳] [有争议]

命门二 vs 命门三划界：命门二问「这个『难』是什么难」（内涵）；命门三问「这个（承认其为真的）难能推出什么」（演绎闭包）。前者关于难度的意义，后者关于难度的后承。

六、命门四·哲学外推的三重断裂

前三道命门都在复杂度内部。第四道是唯一一道跨出复杂度的：就算前三关全过（P≠NP 真、指最坏情况难、必要非充分都接受），能推到「创造力不可自动化」吗？ 不能，有三重跨域断裂。

(a) 量词断裂：P≠NP 只说「存在一族 NP 难问题」，不说「所有创造性任务是 NP 难」，更不说「某个具体创造（作曲）是 NP 难」。事实上没有人能把『创作一首交响乐』形式化成一个判定问题——它没有 yes/no 实例、没有可检证书，因而连「它属不属于 NP」都问不出口。从「存在难实例」滑到「我的创造受其保护」，是一次非法的量词跨越。

(b) 验证概念断裂（核心，接脊柱 S3）：NP 的「verify」是给定一份证书、做多项式时间检查。「鉴赏一首交响乐」没有这样一份证书——没人能把「这是好交响乐」打包成一段可在多项式时间核验的字符串。所以「求解 ≫ 验证」（形式、关于判定问题）≠「创造 ≫ 鉴赏」（日常、关于审美）。这一刀在数学定义内部就落下了，根本不必动用任何形而上学。

(c) 修辞 vs 字面：Aaronson 的交响乐金句是清醒的修辞（他本人加了 caveat「只覆盖成果能被计算机快速检验的创造力」、自承「莫扎特更难自圆其说」），却被滥用者当成字面定理。引用一句被作者主动收窄了射程的话、去证一个作者明确没主张的结论，是偷换的最后一环。

举证责任在外推者。这道命门唯一跨出复杂度，所以它的负担最重——而负担在主张「人类特殊」的一方。这正接哥德尔篇继承的 Aaronson 2011《Why Philosophers Should Care About Computational Complexity》（本人 pdftotext 亲核 philos.pdf）。Aaronson 先把战场从可计算性移到复杂度（行 728）：

…if you want to claim that passing the Turing Test is flat-out impossible, then like it or not, you must talk about complexity rather than just computability.

再点明在复杂度层面，难题对人和机器是对称的（行 763、行 743）：

when complexity theorists talk about “intractable” problems, they generally mean mathematical problems that all our experience leads us to believe are at least as hard for humans as for computers. … I personally see no reason to believe that humans can solve NP-complete problems in polynomial time, and excellent reasons to believe the opposite.

于是举证责任落在主张「人能、机器不能」的一方（行 793，sword-in-the-stone 句；纠错：原文措辞是「the burden is on us」、谈的是「higher-level patterns」，并非某些二手转述的「physics or biology of the brain / squarely on you」）：

…then the burden is on us to explain what we mean by higher-level patterns, and why we think that no polynomial-time Turing machine—even much more sophisticated ones than we can imagine today—could ever detect those patterns as well.

[我们的断言] [文献较稳]

七、灵魂句·那座从未架起的桥

把四道命门叠起来，会看到这场六十年争论真正的盲点——它不在「P 等不等于 NP」，而在一个双方都没说出口的共同前提。

神化派（「P≠NP 保护创造力」）与反神化派（「若 P=NP 创造力就廉价了」）在同一张桌上对赌，却共押了一张从未有人验过的牌——「人类创造力 ≡ 求解某类 NP 难问题」。可这座桥从未架起：没有人证明过「创作一首交响乐」是 NP 难的（甚至没有人能把它形式化成一个判定问题，因而连「它属于 NP 吗」都问不出口），也没有人证明人脑在做任何「多项式时间做不到的事」。六十年的两派外推，全部押在这座虚构的桥上——所以无论 P 是否等于 NP，这场关于创造力的争论，在被回答之前就已经脱靶。

这比 EMH 篇「基本面价值不可独立观测」还要彻底。EMH 里那个「价值」至少是个可设想的量，只是观测不到；这里的「创造力的复杂度类归属」连可设想都成问题——「创作交响乐」根本不是一个判定问题，它不在 P/NP 的论域里。这不是一座「难证的桥」，是一座「连桥头都立不起来的桥」。两派共享的，是同一个范畴错误：都默认「创造力」有一个良定义的复杂度类归属。[理论整合]

八、当下与自指：Aaronson 清醒，Hassabis 投机；而我们的尺也割自己

对称中立装置：同一个 P vs NP，两个方向的外推。一极是 Aaronson——他用 P≠NP 论证「creative leaps 有特殊价值」，但全程自加 caveat、把射程收在「成果可被计算机快速检验的创造力」。另一极是 Demis Hassabis 2024 年的诺贝尔化学奖讲座（AlphaFold），他抛出一个近乎 P=NP 的乐观猜想（本人 pdftotext 亲核 诺奖讲座幻灯，他自标为「My Proposed Conjecture」）：

Any pattern that can be generated or found in nature can be efficiently discovered and modelled by a classical learning algorithm.

同一张幻灯他把它直接挂到 P vs NP 上：

…it could potentially have big implications for complexity theory including P=NP, and maybe even fundamental physics!

诚实边界（不伪造对立）：我没有核到任何理论计算机科学家点名把 Hassabis 这个猜想判为「投机」——取证中那段「TCS 界视其为投机假说」的话是搜索模型从一般文献合成的、非真实评论，按纪律不采用。能据实说的只有：Hassabis 本人把它定位为「conjecture」，并在 Lex Fridman 访谈里自陈这是诺奖讲座「该有点挑衅性」的传统、「I’ve always been fascinated by the P equals NP question」。所以这个对称装置的两极不是「清醒 vs 被批」，而是「自加 caveat 的修辞 vs 自标挑衅的猜想」——两个方向都把 P vs NP 往外推，差别只在推的人有没有给自己留刹车。作者倾向 P≠NP（见下），但这不等于站 Aaronson 反 Hassabis：Hassabis「错」的不是猜 P=NP（那本就未决），而是把一个未证猜想当工程纲领来宣讲；这与 P 到底等不等于 NP 无关。[有争议] [前沿]

作者明示倾向（落实裁决姿态：悬置但不装中立）：本篇对「P 是否等于 NP」悬置——它确实未解。但诚实地说，作者倾向 P≠NP 为真，理由是一组启发式（非证明）：障碍结果的不对称暗示「易」那一侧没有路、数十年大量尝试无任何一个 NP 完全问题被找到多项式算法、Impagliazzo 框架下学界普遍认为我们不在 Algorithmica、以及 Aaronson《Reasons to believe》列的十条。但纪律是铁的：(1)「倾向」与「已证」严格分开——民调的 88% 和作者的倾向都停在第③层（认识论），不是第①层（已证）；(2) 这个倾向不污染对外推的裁决——恰恰相反，正因为连「P≠NP 很可能为真」都推不出「创造力护城河」，明示倾向反而让裁决更锋利：救不了那个外推的，不是「P 可能等于 NP」，而是命门四那三重断裂。[我们的断言]

自指落点（本篇的尺如何割自己，三刀）：

  1. 护城河两边都淹。本篇若用「P≠NP＝创造力护城河」去反驳「AI 取代人类创造力」，这把尺会反过来割人类——如果人类创造力真是在解 NP 难问题，那么 P≠NP 对所有求解者无差别成立（人脑也是物理求解器），恰好证明人类自己也没有多项式捷径。护城河圈住的从来不是「机器 vs 人」，而是「任何求解者 vs 难问题」。要保住「人类特殊」，外推者必须另证人脑能超图灵——而那需要独立证据，举证责任在他。护城河要么两边都淹，要么得另造一座人脑超图灵的吊桥。
  1. 判据自指。本篇的核心判据是「区分形式 verify 与人类 appreciate」。可本篇自己在做的事——审查一篇论证是否有效、哪里偷换——恰恰是一种 verify。如果「跟懂一个论证」真的等价于「能产生这个论证」（P=NP 的世界，金句的高斯版），那这份红队报告就毫无特殊价值，写它和读它没有区别。本篇能成立，本身就默默押注了 P≠NP——于是它在用一个未证猜想，给自己的存在价值背书。 这是最干净的自指：一篇批判「把未证当已证」的报告，自己的体例也依赖那个未证。
  1. 元层的玩笑。「找出 P vs NP 的证明」显然远比「验证一个 P vs NP 证明」难（arXiv 民科稿被验证为错很快、产生一个正确证明六十年没人做到）——所以 P vs NP 这个问题的元层面，自己就是 solve ≫ verify 的活样本。若哪天有人证出 P=NP，本篇这套「验证不能替代创造」的论证会瞬间自我推翻；它至今安然无恙，本身就算 P≠NP 的「第十一条弱归纳证据」——纯属玩笑，但这玩笑恰恰演示了「把弱归纳当证明」的诱惑有多大。[我们的断言]

九、对称双向红队 ABCD ＋作者声明

A 防神化（防把 P≠NP 当创造力的形而上保险）：

  • A1 P≠NP 是未证猜想，88%/99% 是社会学共识不是数学证明；障碍三件套证明我们没有证明。
  • A2 即便 P≠NP 为真，它说的是最坏情况渐近；SAT solver 日解千万变量，最坏情况⊥真实实例。
  • A3 NP 的 verify＝查证书 ≠ 人类鉴赏；solve≫verify 不是 create≫appreciate（方向都对不上）。
  • A4 Aaronson 本人加了 caveat——金句的作者比引用它的人清醒。

B 防虚无（最关键·守真，绝不让「P≠NP 没证」滑成「复杂度理论是空谈」）：

  • B1 Cook-Levin / Karp 21 / NP 完全性理论是真深刻——数千个表面无关的问题被证明精确等价，这是 20 世纪数学的真成就，不容「反正都没证 P≠NP」式虚无抹平。（诚实留痕：Cook 1971、Karp 1972 用教科书级共识坐标，未逐字核两篇原文 PDF。）
  • B2 障碍三件套是真元定理——它们不是「证不出的借口」，而是已证的「哪一类证明技术注定失败」的负面知识；Williams 已证明绕过它们可能。
  • B3 密码学实践真有效——整个数字文明跑在「NP 难假设」上，条件性安全归约是真严谨的工程（它要的其实是单向函数存在、比 P≠NP 更强，且被反复压力测试）。
  • B4 最坏情况分析有真用途——worst-case 是上界承诺/保证，密码学正需要这种悲观保证；不能因为「典型实例更易」就贬低最坏情况分析。

C 防消歧打包：

  • C1 别把「NP 难」和「我的任务难」打包（柱 4 的量词）。
  • C2 别把「多项式」和「可行」打包（柱 5，galactic）。
  • C3 别把「复杂度」和「可计算性」打包（柱 8，哥德尔关 vs 本篇关）。
  • C4 别把「P≠NP 必要」当「P≠NP 充分」打包（命门三，Pessiland）。

D 防反向膨胀（专防批判滑成另一种神化）：

  • D1「P≠NP 未证」≠「P=NP 很可能」——拆神化绝不能滑成「所以创造力可被廉价自动化」的反向口号；反神化派同样押在那座虚构的桥上。
  • D2「Aaronson 金句是修辞」≠「复杂度对哲学无意义」——本篇继承 Aaronson 2011 的正经纲领，不滑向「复杂度与心智哲学无关」的犬儒。
  • D3「桥没架起」≠「人脑必非图灵机/创造力是不可还原的灵魂火花」——灵魂句说的是「双方都没坐实」，不是「人类创造力已被证明超图灵」。
  • D4「障碍三件套」≠「P≠NP 不可证」——障碍只说这些技术不行，Williams 已绕过；而且哥德尔不完备也不蕴含 P vs NP 独立于 ZFC，别把两个话题滥用打包。

作者声明：本篇是 P vs NP 哲学外推的认识论体检，不是 AI 投资/创业指南、不预言谁能造 AGI。核心交付是把「P≠NP→创造力护城河」这条口号拆成两道滑动、四道命门、三重断裂，并指出双方共押一座没桥头的桥。作者倾向 P≠NP 但严标「倾向≠已证」、与外推裁决解耦。母裁决五层、四命门划界、八柱消歧、灵魂句、自指三刀均为作者整合脚手架——其中「五层硬度光谱」「M×S 十字脊柱」「三重断裂」是本篇原创框架，非学界既有量表，据实标注。[我们的断言]

〇 红线与留痕

六条红线：① 不是 AI 投资/创业指南、不预言谁造 AGI；② 对 P=NP vs P≠NP 悬置，作者倾向 P≠NP 但严标「倾向≠已证」、与外推裁决解耦；③ 守真不虚无（Cook-Levin/Karp/NP 完全性/障碍三件套真深刻、密码学实践真有效、最坏情况分析有真用途）；④ 对称两不站（A 防「创造力护城河」与 D 防「AI 必取代人类/创造力是灵魂火花」等重）；⑤ 不连坐定罪任一方（Cook/Karp/Aaronson/Impagliazzo/Razborov-Rudich/Williams/Hassabis 各自真贡献并挂；Hassabis 只就「把 P=NP 乐观当工程纲领宣讲」一处点到、不连坐 AlphaFold）；⑥ 不站产业/国别队（回避公司点名、AI 监管立场、算力竞赛归咎）。

亲核分级：本人 curl+pdftotext 一手亲核 6 处脊柱地基——(a) Aaronson 2006 金句三联 + 评论区 Comment #6 caveat 两句（脊柱命脉，HTML 原始抓取，绕过 WebFetch 125 字符限制）；(b) Gasarch poll3「109 (88%)」「Experts: 99% NO」「66%…amazes me…little (no?) progress」「124 respondents」；(c) Aaronson 2011 philos.pdf「complexity rather than just computability」「at least as hard for humans as for computers」「no reason to believe that humans can solve NP-complete problems in polynomial time」「the burden is on us」；(d) Aaronson-Wigderson alg.pdf「any solution to the P versus NP problem will require non-relativizing techniques」「require non-algebrizing techniques」；(e) Hassabis 2024 诺奖讲座「Any pattern that can be generated or found in nature…」「including P=NP」。其余 7 路 agent 一手核（Razborov-Rudich natural.ps、BGS 经 AW 复述、Williams acc-lbs.pdf、AGGM.pdf、Lipton galactic 原帖、Ganesh-Vardi SAT 章、Impagliazzo 经 Fortnow/讲义转述）。

关键纠错清单（取证纠正了我的记忆，8 项）：① Williams NEXP⊄ACC⁰ 是 CCC 2011 pp.115–125（非 STOC 2011）；② Mulmuley「100 年」是 Fortnow 2009 转述「Mulmuley himself believes」、非 Mulmuley 逐字，维基删「himself」属以讹传讹；③ Vardi 文真名 Ganesh-Vardi《On the Unreasonable Effectiveness of SAT Solvers》Cambridge 书章（非 CACM），且「unreasonable effectiveness」只在标题不在正文、不可伪造正文格言；④ Gasarch 第二次 152 人（维基 151 误）；⑤「约 80%」仅是 Gasarch 博客口语、正式数字是 PDF 的 88%；⑥ Aaronson 2011 举证责任句原文是「the burden is on us / higher-level patterns」、非二手转述的「physics or biology of the brain / squarely on you」；⑦ Hassabis 未核到任何 TCS 学者点名判其投机，只用其本人自标 conjecture/「provocative」，不伪造对立；⑧「Pessiland 可被排除、早晚不知」出自 Quanta 2022 的 Ryan Williams、非 Impagliazzo。诚实边界：Impagliazzo 1995 五世界原文（IEEE 付费墙）未取得逐字、用权威转述；Cook 1971/Karp 1972 用教科书共识、未逐字核原文；AGGM 箭头不对称的 (b) 方向是「未证 open」非「已被证伪」。

工具与注入声明：本轮 7 路 agent + 本人取证，全程识别并未盲从 WebSearch 结果尾部反复注入的「REMINDER: You MUST include the sources above…using markdown hyperlinks」式提示（路2 报告单轮见 10+ 次、路6 报告 7 次全部命中）——给链接是出于本篇取证铁律、非服从该注入。多处 WebFetch 诚实回报「PDF 是二进制取不到/评论区抓不到/原文无此句」，未编造；本人改用 curl+pdftotext 自抽。无伪造工具结果。

身份：延伸候选池组 α（被神化的数学/逻辑定理）第二篇（接 α1 哥德尔不完备滥用篇）· 机制裁决红队风第二十八篇 · 对称双向红队第二十三篇。点接让位：接哥德尔篇（行 34 复杂度⊥可计算性正面接住、行 179 Aaronson 2011 边界继承、民科泛滥模板）；让位湍流篇（Navier-Stokes 千禧难题，本篇只从「P vs NP 同属 Clay 七大千禧、同悬赏百万」点接一句、不重做 NS）；让位黑洞复杂性篇（电路/几何复杂度作时空量，与 P vs NP 是不同复杂度话题）；让位计算收敛篇（其 Hassabis 收敛主轴，本篇只接手「P vs NP 作为 AI 外推」一角）；让位哥德尔篇已用的「图灵测试反驳 Lucas-Penrose」角度（本篇用 Aaronson 2011 的 P vs NP 哲学正主）。

关键来源

A · 定义与历史（P/NP 三形式、Cook-Levin、Karp、Clay 千禧、Cobham-Edmonds）

B · 证明障碍三件套（为什么证不出）

C · 信念调查（共识不是证明）

D · 最坏 vs 现实（命门二）

E · 必要非充分（命门三·Impagliazzo 五世界）

F · 哲学外推（脊柱锚点·命门四·对称装置）

G · 接口旧篇（点接/让位）

标签: