TC^0 is a highly restrictive complexity class for constant-depth threshold circuits with polynomially many gates and bounded fan-in. It describes what can be computed under severe limits, not how quickly every computation runs. section 7.4
For large language models, generating a response is described as falling within TC^0. Longer intermediate reasoning can move the computation toward P, but problems in NP or harder remain out of reach under this framing. section 7.4
Why complexity alone is not enough
A computation requiring n^c intermediate tokens also requires roughly O(n^(2c)) processing time when each token sequence costs O(n^2) to process. Prompt design, training data, and errors add further practical complications. section 7.4
Figure 7.7 A Venn diagram of computational complexities (assuming \(P \neq NP\), a minor point for the nerds) relate to each other. The top arrows give examples of the kind of problem that a new complexity class lets you solve. The bottom arrows show where LLMs land in terms of their complexity.
Use the complexity diagram to compare TC^0, P, NP, and the kinds of problems associated with each boundary. section 7.4
