Models solve fewer problems after a structural change makes them NP-complete

When one structural detail changes a problem from polynomial-time solvable to NP-complete, can language models adapt their solutions to the new computational structure?

Existing tests did not pair these classes while keeping the problem setting closely matched, leaving that question difficult to isolate.

The authors build P2NPCBench, paired coding problems that test whether models track a structural change from polynomial-time solvable to NP-complete.

The authors compare paired problems across 12 families. Each pair shares a setting, while one structural feature changes whether the problem is polynomial-time solvable or NP-complete. A statement counts as solved only when one generated Python solution passes every test case.

Across 12 models, the mean share of statements solved was 63.8% for polynomial-time problems and 35.4% for NP-complete problems; every model averaged lower on the latter. The paired comparison supports a performance gap associated with the structural change.

The findings cover 12 English-language problem families, P and NP-complete problems, and Python 3 solutions.

Statements were hardened against a fixed four-model panel, related versions appear within lineages, and each evaluated model used one greedy sample; these results do not establish performance beyond that scope.