知识卡片：P 与 NP-完全配对基准——对抗式多智能体重写能否区分“推理”与“记忆”

一句话结论

P2NPCBench 用“同一表层、不同复杂度类”的配对题与对抗式多智能体重写，试图剥离教科书措辞带来的记忆线索；据摘要，12 个模型在 NPC 一侧的 pass@1 显著低于其 P 孪生题（35.4% vs. 63.8%），且加大时间限制收益有限——但正文未能抓取，方法细节与数字均待核实。

事件概述或研究问题

• 研究问题：模型在 P 与 NP-完全（NPC）问题上的表现差距，究竟来自复杂度类本身，还是来自对教科书式题面的熟悉度（回忆而非推理）？
• 动机：许多 NPC 问题存在仅差一个结构细节的多项式时间“孪生题”（如 3-着色 vs. 2-着色）。若模型真在推理，应能识别问题落在边界哪一侧；但现有基准要么固定题面措辞，要么忽略复杂度类标签，因而无法分离这两种解释。
• 产出：基准 P2NPCBench，覆盖 12 个问题族，每个 NPC 题与同表层的 P 孪生题配对。

方法/产品要点

• 构建方式：AgentGAN——对抗式多智能体框架；生成器反复重写题面，直到一组冻结的代码模型失败为止。
• 有效性约束：可执行的有效性门控（executable validity gate）保证每次重写保持答案与复杂度类不变。
• 规模与参照：据摘要为 2,114 条“硬化”题面，并配有人工校验的参考人类解法（hand-verified reference human solvers）。
• 评测：12 个闭源与开源模型。

主要结果或产业意义

• 据摘要：所有模型在 NPC 题面上的得分低于其 P 孪生题（35.4% vs. 63.8% pass@1）；95.1% 的模型族配对在 NPC 一侧失败更频繁。
• 时间限制放大十倍，NPC 准确率仅从 28.5% 升至 31.9%，提示失败源于程序错误或崩溃而非速度不足。
• 硬化（对抗重写）使类间差距从 24.8 个百分点收窄至 14.6 个百分点，作者据此认为原始差距中有一部分反映的是对教科书措辞的熟悉度，而非复杂度类本身。
• 以上数字均待核实（未获取正文）。

为什么重要

• 为“基准分数有多少来自记忆/题面熟悉度”提供了一个可操作的对照设计：同表层配对 + 对抗重写 + 可执行有效性门控。
• 若结论成立，则单纯放宽推理时间预算无法弥补 NPC 侧的性能落差，评测与训练应更关注程序正确性与结构判别，而非仅延长思考。
• 与既有卡片的关系：本卡片处理的是“基准题面与复杂度类的对照设计”；与 TRACE 卡片（配对重放语料上的预测性检验）在“配对设计”方法论上同源，但研究对象、任务与结论完全不同，不构成事实重复。

局限与不确定性

• 正文未抓取，以下均待核实：AgentGAN 的具体智能体角色与停止条件、冻结代码模型清单、“有效性门控”的实现与通过率、12 个问题族的具体名单、人类解法校验流程与规模。
• “pass@1”的判定口径（是否要求程序通过全部测试、崩溃如何计分）待核实。
• 摘要中 35.4%/63.8% 与 28.5%/31.9% 两组数字的评测子集关系待核实。
• 结论的外部效度（是否可推广到非代码类任务、是否对提示格式敏感）待核实。
• 论文编号（arXiv:2610.30103）与日期需以原始页面为准。

可用于图书/PPT/简报的角度

• “同一道题，只差一个结构细节”：用配对题直观展示记忆与推理的差别。
• 基准污染与题面硬化：对抗重写作为去线索（de-cueing）手段的示例。
• “加时间不如改程序”：时间预算与准确率脱钩的证据（待核实后引用）。
• 评测设计方法论：可执行有效性门控如何防止重写改变答案或复杂度类。

原始材料

• 标题：Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
• 来源：arXiv:2610.30103v1
• URL: https://arxiv.org/abs/2610.30103v1
• 关键词（英文原文）：P2NPCBench; AgentGAN; NP-complete; paired P/NPC problems; adversarial multi-agent rewriting; pass@1; benchmark hardening
• 说明：正文未能抓取，本卡片仅基于已知元数据与摘要信息生成，标注“待核实”处需回原文确认。