P2NPCBench
A benchmark for evaluating the algorithmic reasoning ability of large language models, which pairs problems that are superficially similar but differ in computational complexity (P versus NP-complete) to distinguish genuine reasoning from pattern memorization.
Timeline (last 90 days)
P2NPCBench is a new benchmark comprising 12 question families, each consisting of an NP-complete problem and a polynomial-time solvable problem with identical surface wording.
In the P2NPCBench evaluation, 12 proprietary and open-source models achieved an average pass@1 of 35.4% on NPC problems and 63.8% on P twins, a gap of nearly 28 percentage points.
P2NPCBench ultimately produces 2,114 hardened problems, accompanied by human-verified reference solutions.
In 95.1% of model-family pairings, the NPC side has a higher failure rate, indicating that the gap is systematic rather than random fluctuation.
Increasing the time limit tenfold raises NPC accuracy only from 28.5% to 31.9%, indicating that the failures mainly stem from program logic errors or crashes rather than slow execution.
Adversarial hardening narrows the class gap between NPC and P twins from 24.8 percentage points to 14.6 percentage points, suggesting that part of the surface complexity gap stems from models' familiarity with textbook wording.
The benchmark's limitations include: it covers only 12 question families, adversarial rewriting may introduce unnatural wording, and the scale of reference solutions is limited.
All Facts (7)
P2NPCBench is a new benchmark comprising 12 question families, each consisting of an NP-complete problem and a polynomial-time solvable problem with identical surface wording.
50%UnverifiedIn the P2NPCBench evaluation, 12 proprietary and open-source models achieved an average pass@1 of 35.4% on NPC problems and 63.8% on P twins, a gap of nearly 28 percentage points.
50%UnverifiedP2NPCBench ultimately produces 2,114 hardened problems, accompanied by human-verified reference solutions.
50%UnverifiedIn 95.1% of model-family pairings, the NPC side has a higher failure rate, indicating that the gap is systematic rather than random fluctuation.
50%UnverifiedIncreasing the time limit tenfold raises NPC accuracy only from 28.5% to 31.9%, indicating that the failures mainly stem from program logic errors or crashes rather than slow execution.
50%UnverifiedAdversarial hardening narrows the class gap between NPC and P twins from 24.8 percentage points to 14.6 percentage points, suggesting that part of the surface complexity gap stems from models' familiarity with textbook wording.
50%UnverifiedThe benchmark's limitations include: it covers only 12 question families, adversarial rewriting may introduce unnatural wording, and the scale of reference solutions is limited.
50%