模型在NP完全题上明显弱于表面相同的P类孪生题
资讯摘要
论文提出P2NPCBench基准，将12个问题族中的每个NP完全问题与表面表述相同的P类孪生问题配对，并用AgentGAN多智能体框架反复改写题干，直到冻结的代码模型答错，同时用可执行校验保证改写不改变答案与复杂度类别，最终得到2,114条加固题干及人工核验的参考解法。作者报告，12个专有与开源模型在NPC题上的pass@1均低于其P孪生题（35.4%对63.8%），95.1%的模型族配对在NPC侧失败更多；时限放宽十倍仅将NPC准确率从28.5%提升到31.9%，说明失败源于程序错误或崩溃而非速度。加固后类别差距从24.8个百分点收窄至14.6，作者认为部分差距来自对教科书措辞的熟悉而非复杂度类别本身。
要点速读
- P2NPCBench含12个问题族，每个NP完全问题配一个表面相同的P类孪生问题，共2,114条加固题干。
- AgentGAN让生成器改写题干直至冻结代码模型失败，并用可执行校验保持答案与类别不变。
- 12个模型在NPC题上pass@1为35.4%，P孪生题为63.8%；时限放宽十倍仅使NPC准确率从28.5%升至31.9%。
中文摘要由 AI 根据公开来源生成，可能存在理解偏差；具体能力、数字、开放时间等信息请以原文为准。
采集于 2026/10/23 08:00:11（北京时间）。 arXiv 日期为本次公告时间，论文初次投稿日期请查看原文版本记录。