Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
All 12 models scored worse on NP-complete problems than on their polynomial-time twins: 35.4% versus 63.8%.
P2NPCBench pairs problems across 12 families, changing a structural detail that separates the two complexity classes. Its 2,114 statements were adversarially rewritten to strip away textbook cues while preserving answers and complexity classes. Hardening narrowed the performance gap from 24.8 to 14.6 percentage points, suggesting familiar wording explains part of the apparent advantage on easier problems. Giving models ten times longer raised NP-complete accuracy only from 28.5% to 31.9%; the authors attribute failures to incorrect or crashing programs rather than slow execution.
ArXiv · AI/CL/LG's note
P2NPCBench pairs problems across 12 families, changing a structural detail that separates the two complexity classes. Its 2,114 statements were adversarially rewritten to strip away textbook cues while preserving answers and complexity classes. Hardening narrowed the performance gap from 24.8 to 14.6 percentage points, suggesting familiar wording explains part of the apparent advantage on easier problems. Giving models ten times longer raised NP-complete accuracy only from 28.5% to 31.9%; the authors attribute failures to incorrect or crashing programs rather than slow execution.
ArXiv · AI/CL/LG's note
score 5