Imagine you're a high school student who aced every practice test because the questions were recycled from last year's exam. Now the teacher rewrites each problem so the math is identical but the wording is completely unfamiliar. Your score tanks — and the question becomes: did the test get harder, or did you just lose access to your cheat sheet? That's the core mechanism of P2NPCBench. The committed claim: current LLMs perform dramatically worse on NP-complete problems than on their polynomial-time structural twins, but a significant fraction of this gap is explained by familiarity with textbook phrasing rather than genuine sensitivity to computational complexity class. The benchmark — 12 problem families, 2,114 hardened instances, 12 models — is designed to tease apart these two signals. Each NPC problem (say, 3-coloring) is paired with a P twin (2-coloring) on the same graph, so the surface structure is identical and only the complexity-class boundary differs. The adversarial rewriting system, AgentGAN, is where the engineering lives. A generator agent rewrites each problem statement until a panel of frozen code-generating models fails to solve it, while an executable validity gate ensures every rewrite preserves both the correct answer and the complexity class. This is a GAN-style loop but with LLM agents instead of neural generators and discriminators — the generator's fitness is literally 'did you fool the panel,' and the gate's job is 'did you cheat.' The result is problem statements that are semantically and computationally identical to the originals but stripped of the textbook cues that enable recall. The ladder is honest and revealing. Across 12 models (proprietary and open-source), average pass@1 on P problems is 63.8% versus 35.4% on NPC twins — a 28.4 percentage-point gap. But after AgentGAN hardening, the gap narrows from 24.8 to 14.6 points. That 10.2-point compression is the key finding: roughly 41% of the apparent complexity-class sensitivity was just familiarity with standard phrasing. A tenfold time limit increase on NPC problems moved accuracy only from 28.5% to 31.9%, confirming failures are structural (wrong or crashing programs) rather than timeout-driven. Integrity is solid for a benchmark paper. The validity gate is executable — every rewritten instance has a machine-verified correct answer and class preservation, not just human judgment. The 2,114 instances come with hand-verified reference human solvers. The benchmark spans 12 families and 12 models, giving real statistical coverage. The 95.1% figure — the fraction of model-family pairs that fail more on NPC — is a strong aggregate signal. Code is on GitHub. The main weakness: the frozen panel of code models used in AgentGAN could introduce systematic blind spots — if all panel models share the same failure modes, the hardening might be idiosyncratic rather than general. The deeper implication is uncomfortable for the 'LLMs can reason' camp. If you can erase 41% of a model's apparent complexity sensitivity just by rewriting the problem in unfamiliar language, the model's performance on the easy version was never reasoning — it was retrieval. The remaining 14.6-point gap after hardening is more interesting: it could reflect genuine sensitivity to problem structure, or it could reflect that NPC instances are inherently larger or more combinatorially dense in ways that trip up code generation regardless of reasoning. The paper doesn't fully disambiguate these. The obvious next experiment is scaling: test on harder instances within each family (larger graphs, more variables) to see whether the P/NPC gap widens or narrows as instance size grows. If models show constant gaps regardless of scale, that's evidence of structural sensitivity. If the gap collapses at small scales and explodes at large ones, the signal is about code-generation limits, not reasoning. The authors likely didn't run this because instance generation and verification at scale is compute-expensive, and the current paper already represents substantial engineering effort with AgentGAN. This is a natural follow-up paper.
