配对P与NP完全问题的对抗改写基准：模型在NPC侧准确率显著下降
原始标题 / Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
该研究构建P2NPCBench基准，将12类NP完全问题与其多项式时间孪生问题以相同表面措辞配对，并用AgentGAN对抗多智能体框架改写题干以去除教科书线索。结果显示12个模型在NPC问题上通过率仅35.4%，远低于P孪生问题的63.8%，且95.1%的模型对在NPC侧失败更多；时间限制放宽十倍仅将NPC准确率从28.5%提升至31.9%，说明失败源于程序错误而非速度。
01 摘要
作者提出P2NPCBench，通过对抗改写生成2,114条经人工验证的硬化陈述，使NP完全问题与P孪生问题在表面措辞上不可区分。评估12个模型发现所有模型在NPC侧通过率低于P侧（35.4% vs 63.8%），多数模型对表现出此模式，且错误主要来自程序错误而非超时。作者认为类间差距部分源于对教科书措辞的熟悉度，硬化后差距从24.8点缩至14.6点。
02 关键点
- P2NPCBench包含12个问题家族，每个NPC问题与同表面的P孪生问题配对，共2,114条硬化陈述并附人工验证参考解。
- 12个模型在NPC陈述上的pass@1为35.4%，在P孪生上为63.8%，95.1%的模型对在NPC侧失败率更高。
- 十倍时间限制仅将NPC准确率从28.5%提至31.9%，表明失败源于错误或崩溃程序而非运行慢。
回到一手来源
阅读原文 ↗AI GENERATED SUMMARY / DISCOVERED BY ARXIV CS.CL