Computational complexity of reasoning
Which reasoning problems are hard for language models, and why?
We ask whether the systematic failures of model reasoning follow from the computational complexity of the problems themselves, rather than from scale or training, and what complexity theory predicts about where reasoning should break down.