Newest papers

Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting

Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E. Sobhani, Shubhashis Roy Dipta · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.30103 · cited by 0 works (OpenAlex) · open-access PDF

Chinese

许多NP-完整(NPC)问题都有一个多元时间(P)双胞胎,在一个单一的结构细节上有所不同,例如3对2彩绘图。 一个模型,原因而不是回忆应该注意到这个边界的哪一面问题落在,但现有的基准要么修复每个任务的词汇,要么忽略它的复杂性类别,所以他们不能分开两者。 我们引入了P2NPCBench,一个12个问题家庭的基准,其中每个NPC问题与P双胞胎相配,呈现在同一表面上。 为了删除能够回忆的文本提示,我们使用AgentGAN构建它,一个反对的多代理框架,在其中发电机重写每个陈述,直到冻结代码模板失败,而一个可执行的

Machine translation (Meta M2M100); the English original follows.

Abstract

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. The result is 2,114 hardened statements with hand-verified reference human solvers. Evaluating 12 proprietary and open-source models, we find that every model scores lower on NPC statements than on their P twins (35.4% vs. 63.8% pass@1), and that 95.1% of model-family pairs fail more often on the NPC side. A tenfold time limit raises NPC accuracy only from 28.5% to 31.9%, so failures stem from wrong or crashing programs rather than slow ones. Hardening also narrows the class gap from 24.8 to 14.6 points, showing that part of the apparent gap reflects familiarity with textbook phrasing rather than complexity class.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Adversarial system, Notice, Rewriting, Executable, Task (project management), Computer science

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange