Overview
Field: NLP Authors: Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta Published: 2026-10-21 arXiv: 2610.30103
Summary
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.
Key Contributions
- P2NPCBench: a benchmark of 12 problem families in which every NPC problem is paired with a P twin posed over the same surface.
- 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 — removing textbook cues that enable recall.
- The final benchmark contains 2,114 hardened statements with verified human reference solvers.
- All 12 evaluated proprietary and open-source models score lower on NPC statements than on their P twins: 35.4% vs. 63.8% pass@1.
- 95.1% of model-family pairs fail more on the NPC side.
- A 10x larger time limit only improves NPC accuracy from 28.5% to 31.9%, showing failures come from incorrect or crashing programs rather than slow execution.
- Hardening narrows the class gap from 24.8 to 14.6 points, indicating that part of the surface-level gap reflects familiarity with textbook statements rather than genuine complexity-class reasoning.