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.
Figures & tables
Figure 1: Overview of AgentGAN . The generator rewrites each seed, the validity gate Γ admits only answer- and class-preserving drafts, and the frozen discriminator panel tests the accepted variants. Survivors’ shortcuts steer the next round until every discriminator is defeated or d=10 , and the resulting statements form P2NPCBench .
Figure 2: Composition of P2NPCBench . Inner ring: families sized by evaluated statements. Outer ring: NPC/P split within each family.
Figure 3: Length distribution of the statements.
Table 2: pass@1 (%) on P2NPCBench by family; columns 1–12 follow the numbering of Table 1 , and Avg is the macro-average over families. The last row averages each column over all twelve models. Models are grouped by access and ordered by npc average within each group. Within each column, bold marks the best and underline the second-best model (ties share a mark); shading marks each model’s strongest family within each class.
Figure 4: Left: npc pass@1 under time limits. Solid lines are proprietary and dashed lines are open-source models. Center: Accuracy on the seed and on its final hardened variants for each family, with the drop in points. Right: npc versus p pass@1 for each of the 144 model–family pairs (12 models × 12 families). Points below the diagonal fail more often on the npc criterion.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Score
Class
Items
0
1
2
Mean
npc
240
12
77
151
1.58
p
240
8
70
162
1.64
Overall
480
20
147
313
1.61
Appendix
Table 4: Majority-vote score distribution for the 480 sampled statements. Inter-annotator agreement over the 480 statements, each scored by all three annotators, yields a Fleiss’ κ of 0.79.
Score Category
npc
p
Combined
0 (Unfaithful / Error)
0.84
0.87
0.85
1 (Faithful, slight disguise)
0.72
0.76
0.74
2 (Faithful, heavy disguise)
0.77
0.80
0.78
Overall κ
0.76
0.82
0.79
Appendix
Table 5: Detailed breakdown of Fleiss’ κ inter-annotator agreement scores by complexity class and individual score category.
Failure type
Typical cause
npc
p
Macro categories (% of failing cases)
Wrong answer
Program exits cleanly, but its output is rejected by the validator or by exact match against the reference
33.2
46.6
Runtime error
Program terminates with an uncaught exception and produces no usable answer
44.1
23.2
Time-limit exceeded
Program is killed at the per-test wall-clock limit
22.7
30.2
Runtime-error subtypes (% of sampled npc crashes)
Malformed code
48.3
–
Appendix
Table 7: Failure taxonomy. Macro categories give the share of failing test cases per class; npc shares are corrected using the re-run sample. Runtime-error subtypes are measured on the npc crashes only; they sum to 99.4%, and the remaining 0.6% are not attributed to a listed exception.
Family
Wrong + crash
TLE
01 Graph colouring
96.1
3.9
02 Satisfiability
98.6
1.4
03 3-D matching
99.4
0.6
04 Clique / ind. set
81.6
18.4
05 Steiner tree
80.6
19.4
06 Job-shop
95.8
4.2
Appendix
Table 8: Share (%) of each family’s npc failures that are wrong answers (including crashes) or timeouts.
Model
Pass
Wrong
TLE
Crash
Gemini-3.8-Flash
96.0
53.0
4.0
43.0
Qwen3.8-Flash
86.3
53.8
17.8
28.4
Qwen3.8-Omni-Flash
84.4
44.4
9.3
46.3
Mistral-Medium-3.5
74.0
69.4
5.8
24.7
DeepSeek-V4.1-Flash
86.8
48.8
9.1
42.1
Gemma-3-12B
22.1
10.0
69.7
20.3
Appendix
Table 9: Failure signature per model on p , where all three types are recorded directly. Pass is the case-level pass rate; the other columns give the share of each model’s failing cases.
Figure 5: Accuracy along the hardening ladder for npc and p lineages. (a, b) Evaluation-panel pass@1% accuracy at each depth for npc lineages (a) and p lineages (b), on a common y -axis. Families 01–06 (solid lines, circles) reach d10 ; families 07–12 (dashed lines, squares) terminate between d3 and d7 , and an outlined square marks the last depth each reaches. The thick black curve is the overall pass rate for the class. (c) Net drop from d0 to the last depth reached, in percentage points, for each family and class; dashed horizontal lines mark the overall net drops.