PaperlayerView exact revision on arXiv

Source-linked AI summary

Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting

Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta

arXiv:2610.30103v1cs.CL

TL;DR

Existing benchmarks do not test whether models distinguish P from NP-complete problems while holding their surface form fixed. P2NPCBENCH pairs such problems and hardens their wording with AGENTGAN while preserving answers and complexity classes. Across 12 models, pass@1 is lower on NPC statements than on their P twins, and extra time helps little.

  • Problem

    Existing benchmarks do not vary complexity class while holding problem surface form fixed, limiting tests of whether models distinguish P from NP-complete problems.

    Source: §1 · p. 1

  • Method

    P2NPCBENCH pairs P and NP-complete problems across 12 families, using AGENTGAN to adversarially rewrite statements while preserving answers and complexity classes.

    Source: §1 · p. 2, §2.1 · p. 2

  • Results

    35.4% vs. 63.8% pass@1: across 12 models, every model scores lower on NPC statements than on their P counterparts.

    Source: §4.1.2 · p. 6

  • Takeaways & Limitations

    The results suggest that current LLMs often recognize familiar problems rather than reason about their structure.

    Source: §6 · p. 8

    The benchmark covers 12 families and only P and NP-complete problems; all statements are in English and models are evaluated only on Python 3 solutions.

    Source: Limitations · p. 9

Abstract

from arXiv · show

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.

1 Introduction

A model must distinguish polynomial-time problems from NP-complete ones even when a single structural detail separates them. Existing benchmarks do not vary complexity class while holding problem surface fixed, so the paper introduces a paired, adversarially hardened benchmark to test that distinction.

1 Introduction

  • Existing benchmarks either hold wording fixed while spanning complexity classes or rewrite only a few NP-hard problems, leaving class and surface form unvaried together.The paper identifies this as a gap in measuring whether models fail when a problem crosses from P to NP-complete.Source: §1 · pp. 1–2
  • P2NPCBENCH pairs NP-complete problems with polynomial-time twins posed over the same surface, with one structural edit moving between classes.The benchmark contains 2,114 hardened statements and human-verified reference solvers.Source: §1 · p. 2
  • AGENTGAN rewrites statements against a frozen code-model panel while a validity gate preserves each rewrite’s answer and complexity class.This adversarial hardening is intended to remove textbook cues that support recall rather than structural reasoning.Source: §1 · pp. 1–2
  • A tenfold time limit barely improves NPC accuracy, from 28.5% to 31.9%, indicating that failures mainly involve incorrect or non-executable solutions rather than time constraints.The paper motivates this distinction with practical tasks such as routing, scheduling, and network design, where misreading the class can be costly.Source: §1 · pp. 1–2
  • 35.4% versus 63.8% pass@1: across 12 models, every model scores lower on NP-complete statements than on their polynomial-time twins.The paper also reports that hardening narrows the class gap from 24.6 to 14.5 points.Source: §1 · p. 2

2 Methodology

The methodology formulates matched P and NP-complete tasks, then uses an adversarial rewriting pipeline with validity checks to harden them. The resulting benchmark contains 12 families and 2,114 evaluated statements, with class-balanced versions and lineages.

2.1 Problem Formulation

  • Each family pairs an NP-complete criterion with a polynomial-time criterion for the same task, differing in the structural feature that crosses the class boundary.A rewrite must preserve the ground-truth answer and complexity class while removing textbook-recall cues.Source: §2.1 · p. 2

2.2 AGENTGAN Framework

  • The validity gate rejects drafts that alter answers or class, drop bounds or tie-break rules, reveal class or algorithm names, or make a task ill-posed or unsolvable.Accepted candidates must pass executable checks and minimum verifier scores for unambiguity, completeness, faithfulness, and naturalness; the hardening loop can continue to depth 10.Source: §2.1 · p. 2, §2.2 · p. 3, Figure 1 · p. 3
  • AGENTGAN adapts frozen LLM agents as a generator and discriminator panel, adding cross-round memory, an executable validity gate, and an expert council for rejected drafts.The panel is frozen to measure the drop on a fixed model population rather than an equilibrium between changing players.Source: §2.2 · pp. 2–3

2.3 P2NPCBENCH Dataset

  • Reference solvers were tested on full family suites and checked by hand against source semantics, while a 480-statement human audit removed the 20 rewrites judged unfaithful or erroneous.The solver checks had Cohen’s κ = 0.86 between two authors; the rewrite audit had Fleiss’ κ = 0.79 among annotators.Source: §2.3 · pp. 4–5
  • The 12 included families each have a matched NPC/P pair; family selection requires the same problem setting and a single structural feature that changes complexity class.The dataset uses 11 class-disguise strategies, including removing textbook wording, changing scenarios, and reordering constraints; grading uses anchor, corner, and worst-case test tiers.Source: §2.3 · p. 4

2.4 Dataset Statistics

  • 2,114 evaluated statements comprise 1,003 NPC and 1,111 P statements across 12 families, with closely balanced versions, lineages, and test cases between classes.Statements average 378.4 words; NPC statements are slightly longer than P statements, at 390.9 versus 367.1 words on average.Source: §2.4 · p. 5, Figure 2 · p. 5, Figure 3 · p. 5

3 Experimental Setup

The experiments evaluate 12 proprietary and open-source models, each producing a Python 3 solution under shared decoding settings. Performance is measured with pass@1, requiring a single solution to pass every test case.

3.1 Models

  • Twelve proprietary and open-source models each generate one Python 3 solution per statement using temperature 0.0, top-p 1.0, and a maximum of 32,768 output tokens.The hardening pipeline uses a separate generator, discriminator panel, verifier, expert, and held-out model.Source: §3.1 · p. 5

3.2 Metrics

  • pass@1 counts a statement as solved only when the model’s single solution passes every test case, including clean exit and runtime-limit requirements.NPC statements are evaluated at four disclosed limits (1, 2, 5, and 10 seconds); P statements use the limit stated in the problem, set at 2 seconds.Source: §3.2 · pp. 5–6

4 Results and Analysis

Across the benchmark, models perform worse on NP-complete statements than on their polynomial-time twins, and this asymmetry persists after hardening. Extra time helps little, while hardening lowers accuracy on both classes and narrows their gap.

4.1.1 Discriminator Results

  • 41.9% vs. 70.7% accuracy: every discriminator scores lower on final hardened NPC statements than on their P counterparts.The held-out Kimi K3 scores 87% on P and 37% on NPC, a 50-point gap wider than any discriminator's.Source: Table 3 · p. 6, §4.1.1 · p. 6

4.1.2 Benchmarking Results

  • 35.4% vs. 63.8% pass@1: every evaluated model scores lower on NPC than P statements across the benchmark.Gaps range from 9 to 54 points; proprietary models average 62.9% / 91.7% against 26.2% / 54.5% for open-source models.Source: §4.1.2 · p. 6

4.2 Effect of the Time Limit

  • 28.5% to 31.9%: a tenfold time-limit increase raises mean NPC pass@1 only slightly, indicating most failures are incorrect or non-executable rather than merely slow.Proprietary and open-source models gain about 3.5 and 3.3 points, respectively.Source: Figure 4 · p. 7, §4.2 · p. 7

4.4 Directional Asymmetry

  • 137 of 144 model–family pairs fall below the diagonal, with models failing 64.6% of NPC statements versus 36.2% of P statements.The median pair scores 25.5 points lower on NPC; the few reversals cluster in familiar textbook-boundary families.Source: Figure 4 · p. 7, §4.4 · p. 8

4.1.2 Benchmarking Results

  • Linear arrangement and exact cover are the hardest NPC families, while edge colouring remains hard on both sides and 3-D matching has a near-vanishing gap.Within Gemma-3, scaling from 4B to 12B raises NPC accuracy from 7.3% to 26.4% and P accuracy from 16.4% to 43.5%, with no further gain at 27B.Source: §4.1.2 · p. 7

4.3 Hardening Effectiveness

  • −19.5 points on NPC and −29.6 on P: hardening lowers accuracy on both classes, narrowing the gap from 24.6 to 14.5 points.Hardening lineages average 6.62 rounds on P versus 4.96 on NPC; depth and accuracy drop correlate at r = −0.68.Source: §4.3 · pp. 7–8

5 Failure Taxonomy

Failures are classified as wrong answers, runtime errors, or timeouts, with runtime errors the largest NPC failure category and wrong answers the largest P category.

Failure categories

  • Across 1,348,290 graded test cases, 60.9% fail on NPC and 37.6% on P; NPC failures are mostly runtime errors, while P failures are mostly wrong answers.NPC failures comprise 44.1% runtime errors, 33.2% wrong answers, and 22.7% timeouts; P failures comprise 46.6% wrong answers, 30.2% timeouts, and 23.2% runtime errors.Source: §5 · p. 8

Runtime errors

  • Syntax or indentation errors account for 46.5% of crashes, and input-format misreads account for another 27.1%.The authors suggest these crashes indicate that disguised I/O contracts in hardened statements do real work.Source: §5 · p. 8

Failure patterns

  • Timeouts concentrate in exact cover and linear arrangement, causing about 46% of NPC failures in each family.Strong models rarely time out, whereas Gemma-3-12B and 27B time out on 60–70% of their failing P cases.Source: §5 · p. 8

6 Conclusion

The paper introduces paired P and NP-complete benchmark problems and an adversarial framework to harden their wording while preserving answers and complexity classes. Results show persistent class differences, with failures mainly incorrect or non-executable rather than merely slow.

Contribution

  • P2NPCBENCH pairs each NP-complete problem with a polynomial-time variant that differs by one structural detail.The benchmark contains 12 families; AGENTGAN hardens statements while preserving their answers and complexity classes.Source: §6 · p. 8

Conclusion

  • Across 12 models, accuracy falls sharply from P to NPC, extra time barely helps, and a class gap remains after hardening lowers accuracy on both classes.The authors suggest current LLMs often recognize familiar problems rather than reason about their structure.Source: §6 · p. 8

Future work

  • The authors propose extending the benchmark to more families and complexity classes, and using AGENTGAN to harden problems in other domains.Source: §6 · p. 8

Limitations

The benchmark's scope is limited to 12 P and NP-complete families, English statements, and Python 3 solutions.

Scope

  • P2NPCBENCH tests only 12 families and P versus NP-complete problems; classes such as PSPACE are untested.Source: Limitations · p. 9

Evaluation setting

  • All statements are in English, and evaluation uses Python 3 solutions rather than other programming languages.The authors note that faster execution in other languages could change the effect of time limits and the balance between slow correct programs and wrong ones.Source: Limitations · p. 9

Hardening and verification

  • Statements are hardened against a fixed four-model panel, and LLM verification of unambiguity and faithfulness may leave unintended readings.Some evaluated models are close relatives of panel members.Source: Limitations · p. 9

Ethical Considerations

The benchmark pairs polynomial-time and NP-complete variants across 12 families, while related work lacks paired class-and-wording variation. Its family examples show how a single structural change can alter the available algorithm.

Ethical Considerations

  • The dataset contains algorithmic statements, reference solvers, and synthetic tests; sampled rewrites were checked by volunteer undergraduate annotators.The authors judge misuse risk low because rewrites concern algorithmic problems and preserve the correct answer.Source: Ethical Considerations · p. 9

A Related Works

  • Related benchmarks vary wording or cover multiple complexity classes, but none pairs P and NP-complete variants of the same seed.AGENTGAN also adds an executable gate that preserves answers and complexity class while hardening statements.Source: A Related Works · p. 13

B Family Details

  • The family criteria expose different tractable structures: two-literal SAT maps to implications, while interval graphs admit greedy independent-set and sweep-line clique algorithms.The corresponding harder variants allow three-literal clauses or general graphs.Source: B Family Details · pp. 13–14
  • Several pairs change matching structure: pairs yield polynomial-time matching, whereas triples yield three-dimensional matching; exact cover similarly shifts from pairs to triples.For exact cover, the pair case is a general perfect matching, including non-bipartite graphs.Source: B Family Details · pp. 14–15
  • P2NPCBENCH contains 12 matched problem families whose P and NP-complete criteria differ by a single structural feature.Examples include clause width, graph class, and number of machines.Source: B Family Details · pp. 13–14
  • Other pairs hinge on routing or graph restrictions: two-machine flow shop has Johnson’s rule, and tree linear arrangement has a polynomial-time recursive algorithm.General job shop scheduling and linear arrangement on general graphs are NP-complete.Source: B Family Details · pp. 14–15
  • The remaining examples include polynomial-time single-commodity flow, bipartite edge colouring, two-terminal minimum cut, and single-machine precedence scheduling.Their harder counterparts add integral commodities, remove the bipartite restriction, add terminals, or add machines.Source: B Family Details · pp. 15–16

C Detailed Breakdown of Human Verification Scores

This section details the human verification of rewritten statements and the prompts and gates used to generate, check, and evaluate them. It also describes the shortcut-analysis prompt for classifying affordances and identifying shared or fragile model defeats.

C Detailed Breakdown of Human Verification Scores

  • Across 480 sampled statements, rewrites were rarely judged corrupted and were substantially disguised in most cases; agreement was κ=0.79, and all 20 majority-score-0 statements were removed.Table 5 reports consistently high agreement across scores and complexity classes, particularly for identifying corrupted statements.Source: C Detailed Breakdown of Human… · p. 16, Table 4 · p. 16, Table 5 · p. 16
  • Annotators independently compared each rewrite with its original, assigning 0 for unfaithful, 1 for close wording, or 2 for a substantially disguised but faithful rewrite.When unsure whether a rewrite was faithful, annotators were instructed to assign 0.Source: C Detailed Breakdown of Human… · p. 16

D Prompt Templates

  • Prompts use XML-style tags for multiline statements and JSON for parsed shortcut analysis; the same solver prompt serves hardening, validity checks, and evaluation, with code extracted and run.The solver prompt requests Python 3 code only, and its reasoning trace is stripped before execution.Source: D Prompt Templates · p. 16, §D.1 · p. 16

D.2 Evaluation Time-Limit Note

  • NPC evaluation appends a note requiring one solution to be judged under 1-, 2-, 5-, and 10-second limits, while P statements remain unchanged and use their stated limit.Credit at each limit requires both correctness and termination within that limit.Source: §D.2 · p. 17

D.3 Generator Prompts

  • The generator receives the hidden class and intended algorithm and must preserve answers, I/O contract, and class while avoiding class vocabulary and ambiguity.It also receives strategy, intensity, and feedback and memory from prior rounds; the prompt requires at least one consistent rewritten example.Source: §D.3 · p. 17

D.4 Shortcut Analysis Prompt

  • Shortcut analysis examines panel verdicts, reasoning, and solutions to find one affordance shared by surviving models, while tracking prior failures to avoid regressions.The prompt prioritizes a single common affordance so one edit can defeat survivors together; immutable bounds, formats, tie-break rules, and example values cannot be changed.Source: §D.4 · pp. 17–18
  • Annotators mark an affordance immutable with “no” and the task’s intrinsic structure with “yes” for structural_floor, since intrinsic shortcuts cannot be reworded away.The prompt distinguishes core task structure from incidental wording.Source: §D.4 · p. 18
  • Annotators set common_affordance to null unless every surviving model depends on the same affordance; a shared affordance becomes the priority target for one edit.Source: §D.4 · p. 18
  • For each defeated model, annotators mark fragile true when a small wording change could restore its solution and assess which defeated students an edit might accidentally restore.Source: §D.4 · p. 18

D.5 Verifier Prompts

  • A draft passes the verifier only with G1 ≥4, G2 ≥4, G3 = 5, and G4 ≥3, assessing unambiguity, completeness, faithfulness, and naturalness.Faithfulness requires the same task for every input, including bounds, formats, and tie-break rules.Source: §D.5 · p. 18

D.6 Expert Prompt

  • When a draft is rejected, the expert critiques it using the seed and gate diagnostics, proposing concrete fixes while preserving answers, class, I/O contract, and clarity.The expert proposes changes but does not write the final statement or decide whether it passes.Source: §D.6 · p. 18

E Decoding Configuration

Model settings were held fixed within each model throughout the study, and Kimi K3 was reserved as a held-out evaluation model.

E Decoding Configuration

  • Kimi K3 never participates in hardening and is evaluated only on the frozen benchmark, testing transfer to a model the generator did not target.Settings are held fixed per model across families, variants, and depths.Source: E Decoding Configuration · p. 19
  • Table 6 lists model roles and decoding settings; “Reasoning” marks native reasoning mode, “capped” a mandatory reasoning budget, and “default” provider-left parameters.Source: Table 6 · p. 19

F Failure Taxonomy Details

The failure analysis separates crashes, genuine wrong answers, and timeouts, finding that crashes and wrong answers dominate the sampled NPC failures. Reported wrong answers arise from constraint interpretation, algorithm choice, edge cases, formatting, and feasibility errors.

F Failure Taxonomy Details

  • Among sampled NPC wrong-answer cases, 56.7% were crashes, 42.7% genuine wrong answers, and 0.7% borderline-slow runs.These proportions are applied to the 77.8% of NPC failures tagged as wrong answers; the crash share has an approximately ±5.6-point 95% confidence interval.Source: F Failure Taxonomy Details · p. 19
  • Genuine wrong answers recur from constraint misreadings, fragile heuristics, edge-case errors, output-format violations, and incorrect feasibility decisions.Source: F Failure Taxonomy Details · p. 19
  • Timeouts mainly arise from exponential backtracking on worst-case instances, and less often from correct but unoptimised code.Source: F Failure Taxonomy Details · p. 19

G Qualitative Examples

G.1 Edge Colouring

These examples illustrate varied ways programs fail on hardened NPC edge-colouring instances, including incorrect modeling, implementation and output-formatting errors, missing dependencies, and methods that are infeasible for the instance size.

G.1 Edge Colouring

  • The edge-colouring program raises NameError before output because its skeleton tests undefined is_bipartite; its planned backtracking solver is also undefined.It prints an Ellipsis rather than a colouring if execution reaches that output, and its plan targets the bipartite structure of the polynomial twin rather than completing the task.Source: §G.1 · pp. 19–20

G.2 Steiner Tree (OverflowError)

  • With 120 terminals, the Steiner-tree solver’s 2^120-state allocation raises OverflowError before computation; it also misreads the cost bound as a terminal and prints a cost instead of YES/NO.The exact Dreyfus–Wagner method would also require 2^120 subset iterations, and the input shift would cause failure even with few terminals.Source: §G.2 · p. 21

G.3 Linear Arrangement

  • For n = 50, the linear-arrangement solver’s sound subset dynamic program raises MemoryError when its first allocation requests about 1.1 × 10^15 entries.It reads the bound and answer format correctly, but its cut, dp, and parent arrays each scale with the number of vertex subsets.Source: §G.3 · pp. 21–22

G.4 Exact Cover

  • The exact-cover solver times out on 55 triples because it branches on the lowest uncovered element and omits key pruning, despite returning only valid solutions.The passage says timeouts account for nearly half of NPC failures in this family; this instance never prints an answer.Source: §G.4 · p. 22

G.5 Steiner Tree (ValueError)

  • The Steiner-tree program raises ValueError by unpacking three integers from a four-integer header, which includes the cost bound.Its remaining approach enumerates all 2^358 edge subsets and prints a cost rather than the required YES/NO verdict; the passage says input-format misreads make up over a quarter of NPC crashes.Source: §G.5 · pp. 22–23

G.6 Multicommodity Flow

  • The multicommodity-flow program raises ModuleNotFoundError; its implementation imports NumPy and SciPy’s linprog.The test has 8 nodes, 14 edges, and 3 commodities, with a YES reference answer containing an integral flow for every commodity on every edge.Source: §G.6 · p. 23
  • The multicommodity-flow solver fails before input because SciPy is unavailable and models a continuous relaxation without enforcing flow conservation or integrality.Its variable indexing also misattributes printed flows, so the program may return values that do not satisfy the demands or represent a valid flow.Source: §G.6 · pp. 23–24

G.7 Satisfiability

  • The 3-SAT solver crashes with TypeError on a trivially satisfiable no-clause instance, while its clause test also inverts the correct satisfaction rule.The test accepts a clause when any literal is false and rejects it only when all three are true; on the example input, the program reaches output formatting, where str.join receives integers.Source: §G.7 · p. 24

G.8 Precedence Scheduling

Across the scheduling cases, model programs either omit valid schedules or misrepresent task sequencing, producing crashes or incorrect makespans. The examples expose failures in both feasibility search and optimization.

G.8 Precedence Scheduling

  • The solver confuses six tasks with five slots, then enumerates permutations that cannot share slots, so it crashes and could never find the valid YES schedule.The reference schedule assigns the first two tasks to slot 1.Source: §G.8 · pp. 24–25

G.9 Job-Shop Scheduling (Corner Case 1)

  • 40 versus 20 units: input-order greedy scheduling serializes jobs, and machine relabelings do not explore interleavings.The feasible output is not optimal; exact-match grading exposes the error.Source: §G.9 · p. 25

G.10 Job-Shop Scheduling (Corner Case 2)

  • 5 versus 10 units: the program treats machine load as makespan, ignoring within-job precedence that forces operations to run serially.This makes the machine-load value a lower bound, not the true makespan.Source: §G.10 · pp. 25–26

H Accuracy Drop Across Depths

Accuracy declines as hardening depth increases for both classes, narrowing their gap. The decline is steepest early, but family-level responses vary and can reverse the class ordering.

H Accuracy Drop Across Depths

  • NPC accuracy falls 19.5 points (61.4% to 41.9%), while P falls 29.6 points (86.0% to 56.4%), shrinking the gap from 24.6 to 14.5 points.About half of the total drop occurs in the first three steps, and the last three steps barely move the curve.Source: H Accuracy Drop Across Depths · p. 26
  • Every P step is a drop, while the few NPC increases are at most 1.2 points and small enough to be noise.The decline is therefore steady across P depths, with only small NPC upticks.Source: H Accuracy Drop Across Depths · p. 26
  • Families 07–12 lose accuracy two to three times faster per step than families 01–06, and hardening can leave P accuracy below NPC accuracy.Graph colouring loses more as NPC (30.6 vs. 15.8 points), while SAT loses more as P (48.6 vs. 8.7).Source: H Accuracy Drop Across Depths · p. 26

Related papers

Loading 2610.30103v1…