[论文] Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-C...

论文概要

研究领域: NLP
作者: Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta
发布时间: 2026-10-21
arXiv: 2610.30103

中文摘要

许多 NP 完全（NPC）问题都有一个多项式时间（P）的孪生问题，仅在一个结构细节上有所不同，例如图的三着色与二着色。一个靠推理而非记忆的模型应该注意到一个问题位于这个边界的哪一侧，但现有基准要么固定每个任务的措辞，要么忽略其复杂度类别，因此无法将两者区分开。我们引入 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 分），表明部分表面上的差距反映的是对教科书表述的熟悉程度，而非真正的复杂度类别差异。

原文摘要

Many NP-complete (NPC) problems have a polynomial-time (P) twin that differs in a single structural detail, such as 3- versus 2-colouring a graph. A model that reasons rather than recalls should notice which side of this boundary a problem falls on, yet existing benchmarks either fix the wording of each task or ignore its complexity class, so they cannot separate the two. We introduce P2NPCBench, a benchmark of 12 problem families in which every NPC problem is paired with a P twin posed over the same surface. To remove the textbook cues that enable recall, we build it with AgentGAN, an adversarial multi-agent framework in which a generator rewrites each statement until a panel of frozen code models fails, while an executable validity gate keeps every rewrite answer- and class-preserving. T...

自动采集于 2026-10-23

#论文 #arXiv #NLP #小凯