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.
The boundary between P and NP-complete and the recall trap
Complexity theory has long noted that many NP-complete problems admit polynomial-time variants differing by a single structural constraint. Graph 3-colouring versus 2-colouring, or SAT with three clauses per disjunction versus two, are canonical examples. The distinction seems simple in principle, but for a learning system the difference can be subtle: a model trained on textbook phrasing of 3-colouring may simply have memorised associated patterns rather than internalised the underlying logical boundary. Existing benchmarks have compounded this problem by fixing task wording or failing to identify the complexity class of each problem, rendering it impossible to tell whether a model's success reflects genuine reasoning or mere familiarity with problem templates.
P2NPCBench was designed specifically to disentangle these two possibilities. The benchmark assembles 12 problem families, each containing an NPC problem and a P twin posed over the same surface—the same domain, the same types of objects, the same apparent structure—so that the only systematic difference is the complexity-defining detail. This pairing design means that any consistent performance gap between the two versions of a problem cannot be attributed to differences in domain knowledge, feature availability, or surface cues. The benchmark further employs AgentGAN, an adversarial multi-agent framework, to rewrite each problem statement. A generator iteratively perturbs the language of a problem until a panel of frozen code-modelling agents fails to solve it, while an executable validity gate discards any rewrite that alters the answer or the problem's complexity class. The result is a set of 2,114 statements that have been hardened through an automated, reproducible process and then hand-verified against human solvers who confirmed both correctness and class assignment.
AgentGAN: adversarial rewriting with a validity gate
The AgentGAN framework operates as a two-player minimax game. The generator, prompted to rephrase a given problem statement, seeks to produce a version that maximises the failure rate of the frozen code-model panel while preserving the problem's answer space and its classification as either P or NPC. The discriminator—the panel of frozen code models—evaluates each rewrite; if a model produces a correct solution, the rewrite is rejected. An executable validity gate further checks that the rewritten statement remains syntactically valid, that the set of valid solutions is unchanged, and that the problem's complexity class (P versus NPC) is invariant under the rewrite. Only rewrites that pass all three checks—high failure rate for the panel, semantic preservation, and class preservation—are added to the benchmark.
This construction serves a dual purpose. First, it systematically removes textbook cues: the generator can replace formal terminology with paraphrased language, alter variable names, or reorganise the problem narrative, thereby eliminating the surface features that models often latch onto for recall. Second, the validity gate ensures that the benchmark remains a sound test of complexity-class discrimination. Without such a gate, a generator could simply produce ill-formed or trick questions that defeat models for reasons unrelated to P versus NPC distinction. The gate preserves the benchmark's internal validity while still allowing extensive linguistic diversity.
The hand-verification step added another layer of rigor. Human solvers reviewed a sample of the generated statements, confirming that the complexity class was correctly assigned and that no unintended semantic drift had occurred. This step also caught edge cases where the generator's rewrites, though passing the automated gate, subtly changed the problem's intended scope. The final benchmark thus comprises statements that are both adversarially crafted and human‑validated.
Empirical evaluation across model families
The evaluation covered 12 proprietary and open-source models, including recent LLMs and specialised reasoning systems. Each model received the same set of 2,114 problem statements, half drawn from the P twin set and half from the NPC set, presented in random order. The primary metric was pass@1: the proportion of problems for which the model produced a correct solution on its first attempt. Secondary analysis tracked whether failures were due to incorrect output, program crashes, or timeout exceeded.
The results were striking. Every model scored lower on NPC statements than on their P twins, with the aggregate pass@1 dropping from 63.8% for P problems to 35.4% for NPC problems—a gap of 28.4 percentage points. When examining individual model families, 95.1% of model-family pairs exhibited a larger failure rate on the NPC side than on the P side. This near-universal pattern suggests that the difficulty increase is not a quirk of particular architectures but a systematic phenomenon across the board.
Time limits offered a further point of investigation. The authors examined what happens when the allotted time per problem is increased tenfold. Under the extended time limit, NPC accuracy rose only from 28.5% to 31.9%, a modest 3.4‑point gain. By contrast, P-problem accuracy under the same extended time improved substantially, though the paper does not report the exact figure for P problems under the long limit. The limited improvement for NPC problems indicates that the bottleneck is not reasoning time but rather the production of correct, non‑crashing code. Many NPC failures took the form of runtime errors, infinite loops, or outright wrong answers that appeared regardless of how much additional time the model received.
Narrowing the class gap after hardening
One of the most counterintuitive findings concerns the gap between model performance on P versus NPC problems before and after benchmark hardening. Before hardening—using the original, unrewritten problem statements—the gap in pass@1 between P and NPC problems stood at 24.8 percentage points. After hardening through AgentGAN rewriting and the validity gate, the narrowed gap was 14.6 percentage points. In other words, the adversarial process reduced the observed performance gap by roughly half.
This narrowing has a clear interpretation. The original benchmark set contained problem statements that bore the hallmarks of textbook or exam phrasing. Models that had encountered similar problems during pre‑training could solve the P twins more often not because they understood the complexity boundary but because the wording triggered familiar patterns. The AgentGAN generator was specifically tasked with stripping those cues, and the validity gate ensured that the stripped versions remained genuine P or NPC instances. The reduction in the gap therefore reflects the removal of familiarity-based advantages, leaving a truer measure of whether a model can discriminate complexity classes.
The authors emphasise that this does not mean the complexity-class gap disappears. Even after hardening, the NPC advantage gap persists, and models still perform markedly better on P problems. The narrowing simply demonstrates that a substantial portion of the original gap was attributable to surface cues rather than intrinsic reasoning ability.
What the results say about reasoning versus recall
The paper's central claim is that the P versus NPC discrimination task provides a clean probe of whether an LLM reasons about problem structure or relies on memorised associations. The uniform across‑model decline from P to NPC, the minimal gain from more time, and the gap‑narrowing after hardening all converge on the same conclusion: when faced with a problem whose surface has been deliberately varied, models flounder unless they have internally represented the defining structural constraint.
For the field, this has practical implications. Benchmark developers who wish to assess reasoning capabilities must attend to surface diversity; a static set of problems quickly becomes saturated with memorised solutions. The AgentGAN framework offers a method for generating continuously fresh problem variants that remain within a controlled complexity class. Moreover, the finding that time extensions yield only modest gains suggests that investment in better problem representation or architecture may yield larger returns than simply allowing more inference time.
Limitations and trade‑offs
The benchmark's reliance on code‑model panels as the generator's adversarial target means that its effectiveness depends on the composition of that panel. If the panel consists of models with narrow capabilities, the generator may produce rewrites that are easy for more capable models to circumvent, and vice versa. The authors acknowledge this by reporting results across 12 diverse models, but the panel composition remains a potential source of variability.
Another limitation is the scope of problem families. The 12 families cover common NPC categories—graph colouring, satisfiability, bin‑packing, scheduling, and others—but they do not exhaust the landscape of NP‑complete problems. Extensions to less‑studied domains, or to problems where the P‑NPC boundary is less crisp, would be a natural follow‑up.
Finally, the paper's focus is on the first‑attempt success rate (pass@1). It does not explore whether models can eventually solve NPC problems through iterative correction, self‑refinement, or tool use. The 31.9% NPC accuracy under a tenfold time limit leaves open the possibility that with sufficiently powerful self‑correction mechanisms, models could solve a non‑trivial fraction of these problems given enough attempts.
What it means in practice
For developers building or evaluating LLMs, P2NPCBench offers a ready‑made probe of reasoning versus recall. The benchmark can be incorporated into evaluation suites alongside more traditional tests of mathematical ability, commonsense reasoning, or code generation. A model that maintains high pass@1 on the P twins but drops sharply on the NPC twins of each family is likely relying on surface patterns; a model with more balanced performance across the paired sets is more likely to have internalised structural constraints.
The AgentGAN framework itself is reusable. Teams can instantiate a generator using an LLM prompted to rephrase problems, a discriminator panel of their choosing, and a validity gate defined by their problem domain. The authors provide enough detail in the paper for reasonably technical teams to replicate the process, and the hand‑verification protocol ensures that the generated problems remain sound. Over time, such a framework could serve as a moving target for benchmark saturation, a persistent challenge for any field that relies on static test sets.
On a broader policy level, the finding that 95.1% of model-family pairs fail more often on NPC problems signals that the research community's reported capabilities may be overstated if evaluated only on unhardened benchmarks. Any claim that a model "solves NP‑complete problems" should be accompanied by evidence that the model can discriminate the P‑NPC boundary under adversarial paraphrasing, not just on canonical textbook formulations.
A natural ending
P2NPCBench reframes how the community can test whether large language models reason about problem structure or merely recall familiar patterns. By pairing each NP-complete problem with a polynomial‑time twin and hardening the statements through an adversarial multi-agent rewriting process, the benchmark isolates the contribution of surface familiarity to model performance. The results make clear that even sophisticated frontier models struggle when the surface cues are removed, and that the apparent P‑NPC gap narrows considerably once textbook phrasing is stripped away. The framework is open‑source in spirit: any research group can instantiate AgentGAN, define a validity gate for their problem domain, and generate a fresh set of hardness‑tested problems. As the field continues to push LLM capabilities into domains that demand genuine reasoning—planning, theorem‑proving, complex decision‑making—benchmarks like P2NPCBench will be essential for ensuring that progress is real and not merely the result of memorisation.