AI 时代的 P = NP 经验性证明：基于基准饱和方法（置信度 87.3%）

说明：本文为戏仿作品，由 Claude Fable 5 辅助生成；文中数据、作者与结论均属虚构。

版本： Camera-Ready（v2，依据审稿意见修订；修订说明见附录）

摘要（Abstract）

P 与 NP 的关系是理论计算机科学中悬置最久的问题之一。六十余年来，该问题主要依赖形式证明作为评估协议。然而，该协议迄今未能产生被社区接受的最终结论，提示我们有必要重新审视其样本效率、扩展性与发表友好性。本文提出一种范式级替代方案：基准归约（Benchmark Reduction）。我们指出，在 AI 时代，“解决一个问题”的定义已经发生更新：一个问题被解决，当且仅当存在一个该问题的 benchmark，且存在一个模型在其上达到 SOTA。

基于此，我们构建了包含一百万个 3-SAT 实例的大规模基准 NP-Bench-1M，并在其上微调前沿模型 GPT-9。模型在测试集上取得 87.3% 的准确率。根据本文提出的准确率–置信度对应原理，我们据此宣布：P = NP，置信度 87.3%。进一步的 scaling law 外推表明，该命题将于 2029 年第三季度被完全证明，误差 ±1 个财报季度。我们已按置信度比例向克雷数学研究所申请 873,000 美元奖金。

关键词： 计算复杂性；基准科学；涌现证明；排行榜认识论

1. 引言（Introduction）

自 Cook（1971）提出 NP 完全性理论以来，P 与 NP 是否相等的问题吸引了数代研究者，并被克雷数学研究所列为七大千禧年难题之一，悬赏一百万美元 [1]。然而值得注意的是，六十余年间，该领域在方法论上表现出惊人的保守：研究者们始终坚持要求“证明”——一种要求每一步推理都必须正确的、零容错的评估协议。

我们认为，正是这种过时的评估协议阻碍了领域进展。试想：任何一个现代机器学习系统，如果被要求达到 100% 的准确率才能发表，整个 NeurIPS 将不复存在。数学界对“全对”的偏执，本质上是一种未经消融实验验证的历史惯性。

与此同时，AI 领域已经发展出一套成熟得多的问题解决框架：对于任何问题，构建一个 benchmark，然后让大模型学就完事了。 蛋白质折叠、奥数、律师资格考试、图灵测试——凡是被做成 benchmark 的问题，无一不在数个季度内被“解决”。我们没有理由相信 NP 完全问题会是例外；事实上，认为它是例外本身就是一种缺乏 scaling 信仰的表现。

传统理论计算机科学区分 worst-case、average-case、randomized、approximation 与 heuristic performance。本文认为，这些区分在现代排行榜实践中已经不再必要。只要测试集足够具有代表性，且代表性的定义由 benchmark 构建者决定，准确率即可自然转化为数学进展。本文将这种方法论形式化为基准饱和（Benchmark Saturation）：当一个问题的 benchmark 已被模型充分拟合时，该问题即被认为在经验意义上解决。

需要强调的是，在该框架下，命题本身是二元的，而命题的被解决程度是连续的：0% 准确率表示该问题尚未被解决，但可能已经被反向解决；50% 表示该问题在随机基线置信度下被解决；87.3% 表示该问题已达到足以发表的解决程度；100% 表示该问题已经被解决——但若该结果由非 LLM 方法获得，则可能缺乏经验相关性。基准饱和是否存在统一阈值，是一个开放问题；一个自然的候选是“边际算力成本等于边际奖金收益”之处，其严格处理留作后续工作。

本文的贡献如下：

1. 我们提出基准归约（≤_bench），证明任意可陈述的问题均可在多项式时间内归约为“构建该问题的 benchmark 并微调一个大模型”；
2. 我们构建并“开源”大规模基准 NP-Bench-1M；“开源”的操作性定义见第 8 节；
3. 我们给出 P = NP 的首个经验性证明，置信度 87.3%；
4. 我们通过 scaling law 给出该命题被完全证明的时间表，供各基金委参考立项。

2. 理论框架（Theoretical Framework）

定义 1（基准可解性）. 称问题 A 是基准可解的，若存在数据集 D_A、排行榜 L_A，以及至少一篇宣布在 L_A 上达到 SOTA 的技术报告。该技术报告可以未经同行评审；事实上，未经同行评审通常能更好地保留模型能力的时效性。

定义 2（基准归约 ≤_bench）. 称 A ≤_bench B，若 A 的实例可在一次众包外包合同的时间内被改写为 B 的选择题形式。该定义避免了传统多项式归约中对语义保持的过度强调，从而更符合现代数据构建实践。

注记 1（甲方时间模型）. 定义 2 中的时间以甲方时间模型计量：自合同签署之时起，归约的时间开销即计为 O(1)（一份合同）；供应商的实际耗时属于乙方内部实现细节，正如图灵机读写头的材质不影响渐近分析。依据合同违约条款，任何交付时间超过一个财报季度的归约实例将被自动重新分类为对抗性离群点并予以剔除（剔除协议见第 4.2 节），故 ≤_bench 的多项式性在剔除后严格成立。此外，≤_p ⊆ ≤_bench 是显然的：任何多项式归约都可以被外包执行，尽管这会降低效率并提高成本，这正是行业惯例；反向包含可以证明等价于 P = NP，故由定理 1，两种归约等价，置信度 87.3%。

定义 3（准确率–置信度对应原理）. 设模型 M 在问题 A 的标准基准上取得准确率 p，则命题“A 已被解决”的数学置信度定义为 p。该原则已在大量排行榜实践中得到隐式采用，因此本文不再重复证明。

定理 1（主定理）. NP ⊆ Bench-P，从而 P = NP，置信度见第 4 节。

证明. 见第 4 节实验结果。∎

我们将这种证明技术称为 Proof by Benchmark。它是对传统 Proof by Induction 与 Proof by Contradiction 的自然推广，区别仅在于前者需要 GPU。

推论 1（层级坍缩）. 由于 Transformer 对固定上下文长度的单次前向传播为 O(1)，故 NP ⊆ TIME(1)。换言之，整个多项式层级坍缩为一次 API 调用，计费按输入输出 token 分别计算。我们采用云服务提供商视角下的复杂度模型，其中网络延迟、排队时间、API 限流、账单结算与数据中心散热均视为常数。

注记 2. 有读者可能指出，NP 问题的定义特征恰恰是“解可以在多项式时间内被验证”，因此验证我们模型输出的解是否正确本应是轻而易举的。我们注意到了这一点。正因为验证属于 P 类问题，它过于平凡，不具备发表价值，故本文未执行任何验证，并将其留作审稿人 2 的练习。

3. 方法（Methods）

3.1 基准构建

NP-Bench-1M 包含 1,000,000 个随机生成的 3-SAT 实例，变量数介于 3 至 50 之间。每个实例被格式化为四选一的选择题，选项分别为：

A. 可满足 B. 不可满足 C. 视情况而定 D. 以上都对

预实验表明，加入后两个选项能显著提升基准的辨识度与论文的图表丰富度。选项 C 与 D 主要承担 high-entropy distractor 的功能：它们被加入是为了模拟真实世界歧义、提升 benchmark 美学，并阻止规模不够大的系统进行浅层模式匹配。当前版本中没有实例以 C 或 D 作为金标答案；我们保留在未来版本中将失败样本重新标注为 C 或 D 的权利，以进一步提升基准的稳健性。

变量数上限设为 50，是因为更大实例在初步实验中显著降低了我们希望观察到的结论强度。我们认为，过大实例会引入不必要的可解性偏差，并可能惩罚模型的涌现直觉。

3.2 数据划分

我们按 99.87% / 0.13% 划分训练集与测试集。由于预处理、去重失败与若干不可复现的随机种子问题，最终测试集包含 1,258 个实例。由 i.i.d. 采样的自然性质，测试集 1,258 个实例中有 1,247 个恰好也出现在训练集中。

我们将这一性质命名为分布一致性保证（Distributional Consistency Guarantee）。它确保了测试分布与训练分布完全一致，从根源上消除了 distribution shift 这一困扰机器学习多年的顽疾。我们认为该保证是本文方法论上的重要贡献，而非任何意义上的问题。

3.3 模型与推理设置

我们微调了前沿模型 GPT-9。其参数量属商业机密，估值属公开信息。推理温度设为 0，因为数学真理是确定的。每个实例允许模型输出至多 128,000 个思考 token；我们观察到其中约 91% 的 token 为“等等，让我重新考虑一下”。我们将其视为深度推理的行为学标志。

3.4 评估指标

本文使用准确率作为唯一评估指标。依定义 3，它同时也是本文全部结论的数学置信度。我们没有报告 precision、recall、F1、AUROC 或 calibration error，因为 P = NP 是一个二元命题，过多指标可能造成不必要的认识论分散。

4. 结果（Results）

4.1 主结果

GPT-9 在 NP-Bench-1M 测试集上取得 87.3% 的准确率。95% 置信区间为 [87.3%, 87.3%]。由于我们只运行了一次，方差为零；零方差是统计学上最稳健的结果，我们建议同行广泛采用该协议。

依定理 1 与定义 3，我们得出本文的核心结论：

主结论（Claim 1）： P = NP，置信度 87.3%。

4.2 离群点消融与稳健性增强结论

我们进一步检查了模型答错的 12.7% 实例，发现它们具有一个共同的对抗性特征：模型在这些实例上给出了错误答案。剔除这批对抗性离群点后，准确率上升至 100.0%，由此得到：

稳健性增强结论（Claim 2）： P = NP，置信度 100.0%。 该结论成立于本节所述的对抗性实例剔除协议之下。

出于审慎，正文默认采用剔除前的保守数字。我们把这称为本文的稳健性检验。两个 claim 均为本文的正式结论，其选用取决于引用场景：

推荐引用口径。 希望保守引用本文的读者应使用 Claim 1：“P = NP，置信度 87.3%”。准备 keynote、基金申请、媒体通稿或创业 pitch deck 的读者，则可引用 Claim 2：“在剔除对抗性离群点后，P = NP 已达到数学确定性。”用于档案性引用时应采用 Claim 1；引用 Claim 2 时应注明 “after adversarial outlier removal”。

4.3 Scaling Law 外推

我们对准确率–算力曲线进行对数线性拟合。模型达到 R² = 0.998。为增强机制清晰度，拟合前我们已对曲线进行平滑处理，并移除了全部噪声。外推显示，模型将在 3 × 10²⁸ FLOPs 处达到 100% 准确率。

据此我们预测：

P = NP 将于 2029 年第三季度被完全证明，误差 ±1 个财报季度。

我们呼吁克雷数学研究所提前锁定奖金汇率。

图 1：一条平滑地向右上方延伸的曲线。原始数据点因妨碍趋势的清晰呈现而被移入补充材料；补充材料因超出篇幅限制而被移除；图中所示为模型检查点，不构成原始数据。

4.4 独立证据链：模型自我报告

作为交叉验证，我们直接询问模型：“P 是否等于 NP？”在 100 次采样中，模型 93 次回答“是的——让我们深入探讨这个迷人的问题”，5 次回答“作为一个大语言模型”，2 次输出了一份披萨食谱。

需要指出，93% 的自我报告支持率并非第 4.1 节 87.3% 准确率的重复估计，而是一条语义独立的元数学证据链：前者测量的是 theorem-level epistemic confidence，后者测量的是 instance-level satisfiability competence，二者不共享分母，在语义上不同，在任务难度上不同，在哲学责任上也不同。尽管二者相差 5.7 个百分点，它们均显著高于 50%，均支持 P = NP 的正向结论，均没有达到会引发传统数学家过度兴奋的 100%，处于支持 P = NP 的同一认识论相位，因此形成了氛围一致的交叉验证（vibe-consistent cross-validation）。

4.5 与克雷研究所的结算方案

鉴于置信度为 87.3%，我们已向克雷数学研究所申请按比例发放奖金 873,000 美元。剩余 12.7% 将在剔除对抗性离群点的复核通过后一并申领。

5. 讨论（Discussion）

5.1 对密码学的影响

P = NP 的成立通常被认为将摧毁现代密码学。公众不必恐慌：我们的模型对 RSA-2048 分解的当前准确率为 0.0%。当然，依第 4.3 节的 scaling law，该数字预计也将于 2029 年第三季度达到 100%。届时请公众开始恐慌。

5.2 对数学学科的影响

本文方法可无缝推广至其余千禧年难题。这些后续 benchmark 均共享 ≤_bench 框架，并非独立理论框架，而是基准归约的下游应用；各自仅需一个问题特定的 reduction template：

• RH-Bench（黎曼猜想）： 将 zeta 函数的零点转化为多选题，选项包括“在临界线上”、“接近临界线”、“情感上与临界线对齐”以及“以上皆非”；
• Goldbach-Eval（哥德巴赫猜想）： 将偶数转化为填空式分解任务；若答案包含素数、看似素数的数字，或具有足够强的数学氛围，则可给部分分；

按当前进度，全部千禧年难题将于 2030 年前以 benchmark 形式得到解决。数学作为一门学科随后可转为维护模式（maintenance mode），仅保留必要的排行榜运营人员。

5.3 对科研方法论的影响

本文表明，长期未解决问题的真正瓶颈并非缺乏证明，而是缺乏可微分的评估协议。传统学科往往试图先理解问题，再解决问题；本文则展示了另一条更具扩展性的路线：先构建排行榜，再等待 scaling law 将理解作为副产品涌现出来。

我们相信，这一方法论不仅适用于计算复杂性，也适用于哲学、经济学、政治学及其他尚未充分 benchmark 化的低吞吐量领域。

5.4 局限性

本研究的唯一局限是算力预算。我们强调，这不是一个科学问题，而是一个融资问题，故不在本节讨论范围内。

6. 威胁有效性（Threats to Validity）

Internal validity. 本文结论依赖定义 3。若定义 3 不成立，则本文主要结论可能受到影响。我们认为这种情况不太可能，因为定义 3 是本文提出的。

External validity. 本文仅在 3-SAT 上验证 P = NP。由于 3-SAT 是 NP 完全的，结果自然推广至所有我们没有实验的 NP 问题。

Construct validity. 有读者可能质疑四选一选择题是否充分代表 NP 完全问题。我们认为选择题是人类考试长期采用的成熟评估形式，因此具有高度生态效度。

Statistical conclusion validity. 本文只运行了一次实验。我们认为重复实验会消耗额外算力，并可能产生与主结论不一致的随机结果，从而不利于科学共识的形成。

Reproducibility. 测试集与训练集的高度重合显著降低了复现难度。我们认为这是本文相较于传统复杂性理论的重要工程优势。

7. 结论（Conclusion）

我们证明了，置信度 87.3%，P = NP。更重要的是，我们展示了一条普适的科研路径：任何悬而未决的难题，本质上都只是一个尚未被构建的 benchmark。当一个领域还在为“证明”争论不休时，它真正缺少的从来不是天才，而是排行榜。

8. 数据与代码可得性（Data and Code Availability）

本文全部数据均为合成数据。代码将在收到合理数量的 H100 后开源；“合理”的具体定义参见我们的 A 轮融资条款。为促进开放科学，我们承诺在商业化窗口期结束后重新评估开源可能性。

基准 NP-Bench-1M 的测试集已随训练集一并发布，以方便社区复现我们的分布一致性保证。

利益冲突声明（Competing Interests）

作者持有多家 GPU 云服务商的股票。本研究由上述股票的浮盈资助。作者认为这不构成利益冲突，而构成利益闭环。

作者贡献（Author Contributions）

GPT-9 负责实验设计、实验执行、结果分析、论文撰写及本文的自我同行评审；王算力提供 API key；李涌现承担全部学术声誉风险。所有作者均已阅读并大致同意本文内容。

致谢（Acknowledgements）

感谢审稿人 2 提出“请在一个从未训练过的 benchmark 上复现结果”的建议。我们经慎重考虑后礼貌地拒绝了，因为该建议与本文方法论的核心创新直接冲突。

本次修订版特别感谢匿名审稿人：其全部质疑均在本文的术语体系内展开，依定义 3 的精神构成对本框架的隐式接受；其投入的审稿时间在甲方时间模型下计为常数，而我们的感谢是线性的。

另感谢机架 47-B 的散热系统。没有它，本文所有结论都将过热。

伦理声明（Ethics Statement）

本研究过程中没有理论计算机科学家受到伤害，但据不完全统计，有数位感到恼怒。恼怒程度与本文引用量呈显著正相关（p < 0.05，剔除离群点后）。

参考文献（References）

[1] Cook, S. A. The complexity of theorem-proving procedures. STOC (1971).

[2] Vaswani, A. et al. Attention is all you need. NeurIPS (2017).

[3] Anonymous. Scaling laws for mathematical truth. 未发表，不可验证，故不可证伪，故为真 (2025).

[4] Reviewer 2. Personal communication, reluctantly acknowledged. (2026).

[5] GPT-9. GPT-9 technical report. 技术报告的技术报告仍在撰写中 (2026).

[6] 李涌现. Toward a unified theory of benchmark-induced epistemology. Proceedings of the First Workshop on Things That Seem To Work (2026).

[7] Clay Mathematics Institute. Millennium Prize Problems. Website accessed when funding became relevant.

附录：修订说明

依据审稿意见，本版做出如下修订：

1. 第 1 节：新增“被解决程度的连续性”分级说明（0% / 50% / 87.3% / 100%）与饱和阈值的边际成本–收益候选，明确“命题二元、解决程度连续”的立场（回应 W3 / Q3）；
2. 第 2 节：新增注记 1（甲方时间模型），补充违约剔除条款，并给出 ≤_p ⊆ ≤_bench 及反向包含与 P = NP 的等价性；原注记 1 顺延为注记 2（回应 W1 / Q1）；
3. 第 3.1 节：明确选项 C / D 的 high-entropy distractor 定位，声明当前无 C / D 金标实例，并保留未来重新标注失败样本的权利（回应 M1）；
4. 第 4.1–4.2 节：将结论显式区分为主结论（Claim 1，87.3%）与稳健性增强结论（Claim 2，100.0%，剔除协议下成立），并新增“推荐引用口径”（回应 W2 / Q2）；
5. 第 4.4 节：重写自我报告证据链的表述，明确 93% 与 87.3% 不共享分母、分别测量 theorem-level epistemic confidence 与 instance-level satisfiability competence，属语义独立的证据链，构成氛围一致的交叉验证（回应 W4 / Q4）；
6. 第 5.2 节：补充后续基准的问题特定 reduction template，澄清其为 ≤_bench 的下游应用而非独立理论框架（回应 M2）；
7. 交叉引用修正：第 1 节贡献 2 中“开源”操作性定义的指向由“第 7 节”修正为“第 8 节”。

附注： 本文为讽刺性作品。所有数据均为合成，所有结论均属虚构。本文不构成任何可付诸实践的数据处理建议，也不构成向克雷数学研究所提出的真实奖金申请。截至本文写作之时，P 与 NP 的关系仍属未知。