Paired P and NP-Complete Problems with Adversarial Rewriting: Models Show Markedly Lower Accuracy on NPC Side
ORIGINAL / Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
The study builds P2NPCBench, pairing 12 NP-complete problem families with polynomial-time twins under identical surface wording, and uses the AgentGAN adversarial multi-agent framework to rewrite statements and remove textbook cues. Across 12 models, pass@1 on NPC problems is only 35.4% versus 63.8% on P twins, and 95.1% of model pairs fail more on the NPC side; a tenfold time limit raises NPC accuracy only from 28.5% to 31.9%, indicating failures stem from incorrect programs
01 ABSTRACT
The authors introduce P2NPCBench, generating 2,114 human-verified hardened statements that make NP-complete problems surface-indistinguishable from their P twins via adversarial rewriting. Evaluating 12 models, all score lower on NPC statements than on P twins (35.4% vs 63.8%), most model pairs show this pattern, and errors mainly arise from incorrect programs rather than timeouts. The authors suggest part of the class gap reflects familiarity with textbook phrasing, as hardening narrows the gap from 24.8 to 14.6 points.
02 KEY FINDINGS
- P2NPCBench contains 12 problem families, each pairing an NPC problem with a surface-identical P twin, totaling 2,114 hardened statements with human-verified reference solutions.
- Across 12 models, pass@1 is 35.4% on NPC statements versus 63.8% on P twins, and 95.1% of model pairs fail more often on the NPC side.
- A tenfold time limit raises NPC accuracy only from 28.5% to 31.9%, showing failures stem from wrong or crashing programs rather than slow runtime.
AI GENERATED SUMMARY / DISCOVERED BY ARXIV CS.CL