结论

联合国际大学、BRAC大学、加州大学河滨分校与马里兰大学巴尔的摩县团队公开预印本《Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting》，提出首个将每个NP完全问题与其仅差一个结构细节的多项式时间孪生题配对的基准P2NPCBench。作者报告称，在12个专有与开源模型上，所有模型在NP完全侧得分均低于多项式时间侧，平均为35.4%对63.8% pass@1，十倍时间放宽仅将NP完全准确率从28.5%提至31.9%。这是作者在受控代码执行评测上的单次报告结论，尚未经过同行评审，也未经本站独立复现，不应视为普遍、因果或可直接用于选型的事实。

研究状态与发布时间

该工作以arXiv预印本形式首次公开，版本为v1。arXiv摘要页记录的提交时间为2026年10月21日17时50分19秒UTC，换算为北京时间为2026年10月22日01时50分19秒，因此归入本次上海日历日10月22日窗口。arXiv当日cs.CL新论文列表明确标注为2026年10月22日星期四的新提交，摘要页与HTML全文页均可确认该时间与版本。论文主题为复杂度感知代码推理评测与基准方法，不涉及商业模型发布、产品功能上线或仓库版本本身，归入研究进展符合收录边界。

研究对象与方法

研究对象是复杂度类别不同但表面形式相近的代码求解任务，例如3着色对2着色、3-SAT对2-SAT、二分匹配对一般匹配等12个问题族。作者认为现有基准要么固定措辞，要么只把复杂度当难度等级，无法分离记忆与推理，因此以配对设计检验模型是否从问题结构选择算法。为去除教科书措辞带来的记忆线索，作者提出AgentGAN对抗硬化框架：单个生成器改写题面，冻结的代码模型 panel 按各自文档推荐的解码配置求解，有效性门只接受保持答案与类别、可解且不泄露类别或算法名的改写。门控分硬约束与分级质量两类，硬约束多为可执行检查，包括参考求解器复现输出、形式约束全量校验与 panel 外模型可解性检验；分级质量由不同于生成器的核验器对明确性、完整性、忠实性与自然度打分，忠实性权重最高。每条种子 lineage 最多硬化至深度10，附带跨轮记忆、激进模式与对抗角落引擎，专家委员会仅点评被拒草稿而不撰写终稿，角色分离在代码中强制执行。编辑理解是：判别 panel 冻结是为了度量固定人群上的难度增量，而非求生成器与判别器的均衡。

评估条件与数据范围

作者称基准共含2114条硬化陈述，每个问题族均有NP完全判据与多项式时间对照，附带人工核验的参考求解器与分层测试用例。种子取自标准NP完全目录而非作者自写，改写保留输入输出契约、界限与平局规则。评测固定12个专有与开源模型，以pass@1为主要指标，在同一测试层级下比较配对两侧，并做时间放宽、硬化前后对比与方向不对称分析。以上范围均来自当日论文内同一套协议，不涉及其他领域数据、真实生产流量与部署成本。

作者报告的主要结果

作者称所有12个模型在NP完全陈述上的通过率均低于其多项式时间孪生题，平均35.4%对63.8%，95.1%的模型与问题族组合在NP完全侧失败更多。十倍时间放宽仅将NP完全准确率从28.5%提至31.9%，作者据此解释失败主要来自错误或不可执行程序而非超时。硬化使两类准确率都下降，但多项式时间侧下降29.6分，多于NP完全侧的19.5分，作者称这说明部分表面类别差距来自对教科书措辞的熟悉度，硬化后类别差距从24.8分左右收窄至14.6分左右。失败分类中运行时错误是NP完全侧最大类型，占44.1%，其中46.5%为畸形或截断代码。以上均为论文内受控评测数值，编辑解释是：配对落后不等于通用能力排序，不构成对其他任务、其他版本或生产选型的保证。

局限与不确定性

本工作为预印本，未经同行评审，结论限于12个问题族、2114条受控改写、12个特定模型快照与代码执行评测，不推广到其他模型规模、编程语言、领域分布与真实业务环境。硬化效果依赖冻结判别 panel 的组成、生成器与核验器的选择、有效性门阈值与深度上限，存在模型选择、提示敏感性与超参敏感性；文本改写难度与类别本身难度的交织仍难完全分离。时间放宽、失败分类与差距收窄均在受控测试层级下报告，人工核验覆盖、参考求解器完备性与长期稳定性仍待验证。引用前需等待独立复现，不应将受控相关性写成因果或已获认可的事实。

潜在意义

若后续复现成立，该路线提示应把复杂度类别与表面措辞一起变化来检验推理而非记忆，配对基准有望为模型迭代指明具体的类别误判短板，并在版本回归时定位退化切片。但在复现与评审完成前，中国读者宜将其视为待验证的研究候选，而非可直接用于采购或部署决策的结论。