Benchmark exposes whether LLMs reason about computational complexity

The paper doesn't establish that LLMs lack reasoning; it shows they fail on adversarially rewritten versions of problems they previously solved. That's a statement about surface-level pattern matching, but it doesn't isolate whether the original success was reasoning or memorization, or whether the rewrite broke the problem itself rather than the model's cognition.

This sits alongside a cluster of recent work probing what models actually compute versus what they claim. The October 20th study on verbalized versus log-probability distributions found models say one thing but output another on 37% of questions, and the same day's minimal-pairs interpretability work showed that failed probes may indicate readout difficulty rather than missing reasoning. P2NPCBench assumes failure under adversarial rewriting proves shallow cognition, but the prior coverage suggests models may encode reasoning in ways standard evaluation methods (including this one) systematically miss or misinterpret.

If AgentGAN-rewritten problems remain solvable when presented to humans or symbolic solvers without loss of correctness, the benchmark measures adversarial robustness, not reasoning. If the same frozen models solve the original P/NP pairs at >80% accuracy but drop below 20% on rewrites, that's evidence of brittle pattern-matching; if they drop to 40-60%, it suggests partial reasoning that degrades under distribution shift rather than absent reasoning.