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.
Most LP-from-text benchmarks are static datasets of word problems written and labeled by hand. Once such a dataset is released, its size is fixed, its difficulty is fixed, and every problem can leak into the training data of future LLMs. We present \textbf{A2utoLPBench}, a benchmark for testing LLM-driven agents on linear programming problems written in plain text. We first pick a feasible point and dual, then write down a problem for which that point is optimal and the objective value is known. The answer is known by construction, with no solver call and no human annotator. The evaluation environment bundles a reference solver-critic baseline and a Docker image whose usage instructions are written for an LLM-driven agent to read. With these in place, any agent can run the benchmark and get a calibrated score with one command. Because the benchmark is a generator rather than a fixed dataset, it has properties no fixed dataset can match: an unlimited supply of fresh problems, a difficulty knob set by (n,m), ground-truth answers correct by construction, low LLM-side cost per problem relative to human authoring, repeatable scores across independent batches, and resistance to training-data leakage when fresh post-cutoff seed ranges are used.
We introduce Pencil Puzzle Bench, a framework for evaluating large language model reasoning through pencil puzzles, a family of constraint-satisfaction problems closely related to NP-complete problems, with deterministic, step-level verification. From a database of 62,231 puzzles across 94 varieties with verified unique solutions, we select a benchmark of 300 puzzles spanning 20 varieties and evaluate 51 models from 11 providers in two modes: direct ask (single-shot) and agentic (multi-turn with iterative verification). A key differentiator of our benchmark is that every intermediate board state can be checked against variety-specific constraints, localizing errors to the exact rule violated, providing the infrastructure for dense, per-move reward signals for process supervision and reinforcement learning. Our evaluation reveals two distinct axes of capability: (1) reasoning effort scaling, where GPT-5.2 improves 81x from no reasoning to maximum effort; and (2) agentic iteration, where Claude Opus 4.6 rises from 0.3% to 30.0% through iterative checking, while GPT-5.2@xhigh improves from 20.2% to 56.0%. Agentic attempts span a median of 29 turns over 17 minutes, with the longest exceeding 1,221 turns and 14.3 hours - a demanding test of long-context utilization, not just reasoning.
Large language models still struggle with contest-level programming, while many agentic remedies rely on massive inference-time sampling or expensive multi-stage post-training. We study when execution feedback reliably helps an LLM CP solver and which mechanisms govern the gains. We model feedback-driven solving as a calibrated stopped process and identify three quantities: false-admission risk, program-level evidence against bad programs, and the active-state success hazard. Under held-out trace calibration and selection from a pre-declared finite controller manifest, the resulting structural certificate lower-bounds the clean success probability before false admission. We instantiate mechanisms targeting these quantities as Dual-Granularity Verification, Test Augmentation, and Experience-Driven Self-Evolving, yielding CP-Agent. Without updating any parameters, CP-Agent raises Pass@1 from 25.8% to 48.5% on LiveCodeBench Pro and improves Refine@5 by 11.0% on ICPC-Eval. Across three LLM backbones, CP-Agent lies on the cost--accuracy efficiency frontier, and ablations show that each component primarily affects its corresponding certificate quantity.
Peisong Wang, Bowen Liu, Zehua Li +4
The Hong Kong University of Science and Technology (Guangzhou) Guangzhou, China