arXiv cs.CL· Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta·· 12 小时前AI 评分34
P2NPCBench：用对抗式多智能体重写检验 LLM 能否区分 P 与 NP-Complete 问题
Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
AI 导读
研究者提出 P2NPCBench，包含 12 个问题族，每个 NP-complete 问题都配一个表面相同、仅结构细节不同的 P 版本，并用对抗式多智能体框架 AgentGAN 重写题目以去除教科书线索，最终得到 2,114 条加固陈述。
正文 · AI 翻译
摘要：许多 NP 完全（NPC）问题都有一个多项式时间（P）的孪生问题，二者仅在某一个结构细节上不同，例如图的 3-着色与 2-着色。一个能够推理而非仅靠记忆的模型应当能判断一个问题落在这条边界的哪一侧，然而现有基准要么固定每个任务的措辞，要么忽略其复杂度类别，因此无法将二者区分开。我们提出 P2NPCBench，这是一个包含 12 个问题族的基准，其中每个 NPC 问题都配有一个在相同表层表述下提出的 P 孪生问题。为消除那些使记忆成为可能的教科书式线索，我们用 AgentGAN 构建该基准，这是一个对抗性多智能体框架，其中生成器会重写每个陈述，直到一组冻结的代码模型全部失败，同时一个可执行的合法性校验保证每次重写都保持答案和类别不变。最终得到 2,114 条加固后的陈述，并配有经人工核验的参考人类求解器。在评估 12 个专有和开源模型后，我们发现每个模型在 NPC 陈述上的得分都低于其 P 孪生陈述（pass@1 为 35.4% 对 63.8%），并且 95.1% 的模型族配对在 NPC 一侧的失败率更高。将时间限制提高十倍仅使 NPC 准确率从 28.5% 提升到 31.9%，因此失败源于程序错误或崩溃，而非运行缓慢。加固还将类别差距从 24.8 个百分点缩小到 14.6 个百分点，表明表面差距的一部分反映的是对教科书措辞的熟悉程度，而非复杂度类别。
| 评论： | 此 https URL |
| 主题： | 计算与语言（cs.CL） |
| 引用为： | arXiv:2610.30103 [cs.CL] |
| （或 arXiv:2610.30103v1 [cs.CL] 查看此版本） | |
| https://doi.org/10.48550/arXiv.2610.30103 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Md. Faiyaz Abdullah Sayeedi [查看邮箱]
[v1]
2026 年 10 月 21 日星期三 17:50:19 UTC（2,598 KB）
来源：arXiv cs.CL · arxiv.org