A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
P is the class of languages decidable by a deterministic Turing machine in polynomial time. P represents 'efficiently solvable' problems in complexity theory. Whether P = NP—the most famous open problem in computer science—asks whether fast verification (NP) is equivalent to fast solving (P), with profound implications for cryptography and optimization.
You already know from your Turing machine background that every decidable problem has an algorithm — but that says nothing about how *fast* the algorithm runs. A Turing machine might halt after 2n steps or after 2n steps. Polynomial time is the dividing line between "fast enough to be practically useful" and "too slow to scale." An algorithm runs in polynomial time if its worst-case step count is bounded by some polynomial in the input length: n, n², n³, and so on. The class P collects all languages (equivalently, all decision problems) for which a polynomial-time deterministic Turing machine exists.
Why polynomial specifically? The choice is somewhat pragmatic but defensible: polynomial-time algorithms compose (a polynomial of a polynomial is a polynomial), they scale to large inputs unlike exponential algorithms, and the class P is robust — it doesn't change if you switch between reasonable machine models. The textbook examples you should internalize: sorting a list of n numbers is O(n log n) — in P. Finding a shortest path in a graph is O(E log V) — in P. Multiplying two n-digit numbers is in P. These feel like "problems with known efficient solutions," which is exactly the intuition P captures.
The class NP (nondeterministic polynomial time) contains problems where a *proposed solution* can be verified in polynomial time, even if finding the solution might require searching. The canonical example: given a Boolean formula with n variables, verifying that a particular assignment satisfies it takes linear time — just plug in the values. But finding such an assignment seems to require trying exponentially many possibilities. This asymmetry — easy to check, potentially hard to find — motivates the P vs. NP question.
P ⊆ NP trivially: if you can *solve* a problem in polynomial time, you can certainly *verify* a solution in polynomial time (just re-solve it). The open question is whether NP ⊆ P — whether every problem whose solutions are easy to verify also has an efficient algorithm to *find* solutions. Most complexity theorists believe P ≠ NP, because if P = NP, every cryptographic system whose security rests on computational hardness (RSA, elliptic curves, most of modern security) would collapse. But no proof exists either way, and the question remains the deepest unsolved problem in theoretical computer science.
Your Big-O background makes the technical definition natural: a Turing machine runs in time O(nk) for some constant k. The key shift from algorithm analysis to complexity theory is that here, you're classifying *problems* rather than specific algorithms — a problem is in P if *any* polynomial-time algorithm exists, not necessarily a particular one. This reframing from "how fast is this algorithm?" to "what is the intrinsic computational difficulty of this problem?" is the core conceptual move of complexity theory.