P2NPCBench:用对抗性多智能体重写检验 LLM 在配对 P 与 NP 完全问题上的真实推理能力
研究者推出 P2NPCBench 基准,将 12 个问题族中的 NP 完全问题与同表面的 P 问题配对,并用 AgentGAN 对抗性多智能体框架改写题目以消除教科书式提示,生成 2,114 条经人工验证的题目。评测 12 个专有与开源模型发现,模型在 NP 完全题目上的 pass@1 为 35.4%,显著低于 P 题的 63.8%;十倍时间限制仅将 NP 完全准确率从 28.5% 提升至 31.9%,说明失败源于程序错误而非速度,且对抗性加固使复杂度类差距从 24.8 收窄至 14.6 分。