the class P
/ pee /
Imagine sorting a stack of bills, looking up a word in a dictionary, or finding the shortest route on a map. As the input grows, the work grows too, but gently — twice the data, maybe four times the work, not a million times. P is the club of all decision problems (yes/no questions) that can be solved this 'gently growing' way: there is an algorithm that always gives the correct yes/no answer, and its running time is bounded by some polynomial in the input size, like n, n^2, or n^3.
Precisely, a decision problem is in P if there exist constants c and k and an algorithm that, on every input of size n, halts with the right answer within c * n^k steps (in a reasonable model like the RAM model, under a reasonable binary encoding). The key word is SOME polynomial — n^2 and n^100 are both allowed, and the class does not care which. Why draw the line at polynomials rather than, say, at n^3? Because polynomials are exactly the running times that stay manageable as inputs scale and that are closed under composition: if you call a polynomial-time subroutine a polynomial number of times, the whole thing is still polynomial. That robustness is why 'polynomial time' became the standard mathematical stand-in for 'efficiently solvable'.
P is the home of almost every algorithm in a first course: sorting (O(n log n)), shortest paths (Dijkstra), maximum flow, matching, primality (the AKS test). Two honest caveats. First, 'polynomial' is a coarse, asymptotic ideal: an n^100 algorithm is in P but useless in practice, and a 2^(0.0001 n) algorithm, though not in P, might beat it on real inputs — P captures scaling, not a promise of speed at every size. Second, P is defined for decision problems; an optimization problem like 'find the shortest tour' is handled by its decision twin ('is there a tour of length at most B?'), and the two are usually inter-convertible in polynomial time.
'Are two cities connected in this road map?' is in P: run breadth-first search from one city; if you reach the other, answer yes. On a graph with n nodes and m edges this takes O(n + m) steps — comfortably polynomial in the input size. No matter how the map grows, the time grows only linearly.
P = problems with a guaranteed-correct algorithm running in time c * n^k for some fixed k.
P is about WORST-CASE polynomial time on a deterministic machine. 'Polynomial' is not a synonym for 'fast' — n^100 qualifies — and 'not in P' is not a synonym for 'slow in practice'; the class is a clean theoretical boundary, not a benchmark.