P is the complexity class containing problems solvable by deterministic algorithms in polynomial time. Complexity asks how computation time grows as input size increases; Big-O notation describes that growth. section 7.4
Polynomial-time does not mean instantly or cheaply for every input. It distinguishes comparatively manageable growth from exponential growth, which can make exact solutions impractical as inputs expand. section 7.4
The surrounding complexity examples show the contrast:
- Linear programming is listed with O(n³) complexity, a polynomial-time example. section 7.4
- Prime factorization, traveling salesman, and integer programming are listed with exponential complexity, illustrating harder growth. 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-class diagram to place P beside related classes and compare those classes with LLM computation. section 7.4
