LLMs fail to recognize computational complexity boundaries even when problems differ only structurally—they score 28 points lower on NP-complete problems, and this gap persists even with more computation time, indicating reasoning failures rather than speed issues.
This paper introduces P2NPCBench, a benchmark that tests whether LLMs can distinguish between polynomial-time solvable problems and NP-complete problems by pairing them with identical surface structure. Using an adversarial rewriting framework called AgentGAN, researchers created 2,114 hardened problem statements that remove textbook cues.