P2NPCBench: When LLMs Face Paired P and NP-Hard Problems, Their True Reasoning Ability Is Revealed

Large language models perform impressively on programming and algorithm tasks—but are they truly "reasoning," or merely pattern-matching against memorized textbook templates? A new benchmark called P2NPCBench delivers a sobering answer. Researchers constructed 12 problem families, each containing an NP-complete (NPC) problem and a polynomial-time (P) solvable "twin" with identical surface phrasing, then stripped away textbook cues through adversarial multi-agent rewriting. The results: across 12 proprietary and open-source models, pass@1 on NPC problems was only 35.4%, while on their P twins it reached 63.8%—a gap of nearly 28 percentage points.

Problem Design: Pairing P and NPC Problems to Strip Away Memorization Cues

Many NP-complete problems have a polynomial-time version that differs by just one structural detail—for example, 3-coloring versus 2-coloring of a graph. In theory, a model that truly understands complexity boundaries should be able to distinguish the two; but existing benchmarks either fix task wording (making memorization easy) or ignore complexity class altogether, failing to separate reasoning from recall.

The core innovation of P2NPCBench is "same-surface pairing": every NPC problem is paired with a P version written in an identical style. To prevent models from "recognizing" problems through familiar textbook phrasing, the team developed AgentGAN—an adversarial multi-agent framework. A generator agent repeatedly rewrites problem statements until a frozen set of code models collectively fail; meanwhile, an executable validity gate ensures each rewrite preserves both the answer and the complexity class. The final output is 2,114 hardened problems, accompanied by human-verified reference solutions.

NP-complete (NPC) is a core concept in computational complexity theory. A problem belongs to the NP class if its solution can be verified in polynomial time; an NP-complete problem is the hardest kind in NP, such that any NP problem can be reduced to it in polynomial time. Classic examples include the decision version of the Traveling Salesman Problem, the Boolean Satisfiability Problem (SAT), and the 3-coloring problem for graphs. The polynomial-time (P) class, by contrast, contains problems solvable in polynomial time. Whether P equals NP is one of the most important unsolved problems in computer science. For language models, distinguishing whether a problem is P or NPC is crucial: NPC problems typically require exponential search or heuristic approximation, whereas P problems admit efficient exact algorithms. Thus, superficially similar P/NPC pairs can effectively test whether a model truly understands a problem's computational difficulty, rather than merely matching surface patterns.

AgentGAN is an adversarial multi-agent framework for automatically rewriting problem statements to remove memorization cues. Its core idea borrows from generative adversarial networks (GANs): a generator agent rewrites problems, while the discriminator consists of a set of frozen code models that answer the rewritten problems. The generator's goal is to produce problems that make these models collectively fail, while an executable validity gate ensures the rewrites do not change the problem's answer or complexity class. This adversarial training process forces the rewritten problems to remain semantically equivalent while eliminating surface patterns (such as fixed textbook phrasing) that models might rely on. AgentGAN's output is human-verified, ultimately yielding 2,114 hardened problems. This method effectively disentangles a model's familiarity with phrasing from its true reasoning ability.

Key Findings: The Performance Gap and the Familiarity Trap

In evaluations across 12 models (both proprietary and open-source), every model scored lower on NPC problems than on their P twins. On average, NPC pass rate was 35.4%, versus 63.8% for the P versions. More critically, in 95.1% of model-family pairings, the NPC side had a higher failure rate. This indicates the gap is not random fluctuation but systematic.

Researchers further tested the effect of time limits: increasing the time limit tenfold raised NPC accuracy only from 28.5% to 31.9%. This means failures stem primarily from program logic errors or crashes, not from slow execution—the models weren't "thinking too briefly," they were "thinking wrong."

Interestingly, adversarial hardening actually narrowed the class gap: from 24.8 percentage points to 14.6 percentage points. This suggests that part of the apparent complexity gap actually stems from models' familiarity with textbook phrasing, rather than genuine understanding of complexity class. Hardening removed these cues, allowing the gap to more truthfully reflect reasoning ability.

pass@1 is a commonly used metric in code generation evaluation, representing the proportion of models whose first generated candidate program passes all test cases. In P2NPCBench, pass@1 measures a model's accuracy on its first attempt at each problem. Unlike pass@k (which allows generating k candidates and counts a success if any one passes), pass@1 more strictly reflects the accuracy of a model's single-shot reasoning. This metric is sensitive to temperature sampling and typically needs to be evaluated under low-temperature or greedy decoding. P2NPCBench reports an average pass@1 of 35.4% on NPC problems and 63.8% on P twins—a statistically significant gap indicating that models' ability to solve NPC problems in a single attempt is far below that for superficially similar P problems.

Implications for AI Programming and Model Evaluation

P2NPCBench's results cast doubt on current LLMs' algorithmic reasoning abilities. With AI programming assistants now widely used, whether models can distinguish the essential complexity of a problem directly affects their reliability in solving novel problems. If models rely solely on pattern matching, their performance may drop sharply when facing algorithmic challenges that have been reworded or repackaged in the real world.

The benchmark also suggests that evaluating models requires controlling for the confounding variable of "phrasing familiarity." Future benchmark design might more broadly adopt pairing and adversarial rewriting methods to separate memorization from reasoning. For developers, this means model capability cannot be judged solely by scores on standard problem sets; attention should also be paid to performance on de-cued problems.

Limitations and Future Directions

P2NPCBench currently covers 12 problem families, which, while representative, do not exhaust all complexity-boundary scenarios. Adversarial rewriting can remove textbook cues, but it may also introduce unnatural phrasing that affects model comprehension. Additionally, reference solutions are human-verified, limiting scale. Future work could expand the number of problem families and explore more natural hardening methods.

Overall, this study provides strong evidence: LLMs' performance on algorithmic problems still relies heavily on surface familiarity, and genuine complexity reasoning ability remains notably deficient. As model scale grows, how to evaluate and improve this deep reasoning ability will be a key challenge in AI research.

One-line Summary

A new benchmark, P2NPCBench, reveals that LLM algorithm reasoning relies on surface familiarity rather than genuine understanding of complexity.

Paragraph Summary

P2NPCBench paired superficially identical NP-complete problems with polynomial-time solvable problems, using adversarial multi-agent rewriting to remove textbook cues, and tested the algorithmic reasoning of 12 language models. Results show models achieved only 35.4% pass@1 on NPC problems, far below the 63.8% on P twins—a gap of nearly 28 percentage points—and in 95.1% of model-family pairings, the NPC side had a higher failure rate. Increasing the time limit tenfold raised NPC accuracy only from 28.5% to 31.9%, indicating failures stem from logic errors rather than speed. Adversarial hardening narrowed the class gap from 24.8 points to 14.6 points, showing part of the gap stems from phrasing familiarity. The study questions LLMs' deep reasoning ability and suggests evaluations must control for the confounding variable of phrasing familiarity.