问题真的变难了吗：用对抗多智能体重写测试 LLM 的 P
来自 arXiv · 期号 2026-10-22
摘要
很多 NP 完全问题都有一个结构几乎相同、但能在多项式时间内求解的“孪生”版本（比如图的三染色 vs. 二染色）。能真正推理的模型应该能区分这两者，但现有评测要么固定了题目措辞，要么忽略了复杂度类别，无法分离记忆与推理。 这篇论文提出了 P2NPCBench，包含 12 个问题族，每个 NPC 问题都与一个 P 孪生问题配对。为了消除教科书式的记忆线索，他们用 AgentGAN 框架让一个生成器反复改写题目，直到一组冻结的代码模型无法通过，同时用可执行验证门保证改写不改变答案和复杂度类别。最终得到 2,114 道经过人工验证的题目。 评测 12 个模型后发现：所有模型在 NPC 题目上的得分都低于其 P 孪生题目（35.4% vs. 63.8% pass@1），95.1% 的模型-问题族组合在 NPC 侧失败更多。把时间限制放宽十倍，NPC 准确率也只从 28.5% 升到 31.9%，说明失败源于错误或崩溃的程序，而非速度不足。改写还缩小了类别差距（从 24.8 分缩至 14.6 分），表明部分表面差距来自对教科书措辞的熟悉，而非对复杂度类别的理解。