AI TrackerFrontier desk · AEST
Back to news
normalaitech

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

arXiv cs.CL · 22 Oct 2026, 03:50 AEST

A new benchmark called P2NPCBench has been introduced to test models on NP-complete problems paired with polynomial-time twins. The study reveals that models perform significantly worse on NP-complete statements compared to their polynomial-time counterparts.

Key facts

Read aloud

A new benchmark called P2NPCBench has been introduced to test models on NP-complete problems paired with polynomial-time twins. The study reveals that models perform significantly worse on NP-complete statements compared to their polynomial-time counterparts. Many NP-complete NPC problems have a polynomial-time P twin that differs in a single structural detail, such as three- versus two-colouring a graph. We introduce P2NPCBench, a benchmark of twelve problem families in which every NPC problem is paired with a P twin posed over the same surface. Evaluating twelve proprietary and open-source models, we find that every model scores lower on NPC statements than on their P twins thirty five point four percent vs. sixty three point eight percent pass@one. A tenfold time limit raises NPC accuracy only from twenty eight point five percent to thirty one point nine percent, so failures stem from wrong or crashing programs rather than slow ones.

Sources in this cluster