P2NPCBench finds LLMs weaker on NP-complete twins than on P problems
Original title: Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
Twelve models score 35.4% pass@1 on NPC items versus 63.8% on paired P twins; extra time barely helps.
P2NPCBench pairs each of 12 NP-complete problem families with a polynomial-time twin over the same surface form. AgentGAN rewrites statements until frozen code models fail, while a validity gate keeps answers and complexity class unchanged, yielding 2,114 hardened items with hand-checked reference solvers. On 12 proprietary and open-source models, every model scores lower on the NPC side, and 95.1% of model-family pairs fail more often there. A tenfold time limit lifts NPC accuracy only from 28.5% to 31.9%, and hardening narrows the class gap from 24.8 to 14.6 points.
- Twelve families; 2,114 hardened statements with hand-verified solvers.
- NPC pass@1 is 35.4% versus 63.8% on the P twins.
- Tenfold time limit moves NPC accuracy from 28.5% to 31.9%.
- Hardening shrinks the P-versus-NPC gap from 24.8 to 14.6 points.
- Products
- P2NPCBenchAgentGAN
From the original article
1 min read at arxiv.orgMany 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.
By Nurul Labib Sayeedi · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.