P

P (Polynomial time) is the complexity class of decision problems solvable by a deterministic Turing machine in time polynomial in the input size. It is the baseline class of "efficiently solvable" problems — the theoretical boundary between what can be computed in practice and what cannot. P contains the problems we know how to solve without brute force: sorting, shortest paths, primality (via the AKS test), linear programming, and most problems taught in undergraduate algorithms courses.

The definition of P is remarkably robust across computational substrates. A problem is in P whether solved by a Turing machine, a Boolean circuit, a cellular automaton, or a modern processor. This substrate-independence is not accidental; it reflects the Church-Turing Thesis extended to efficient computation. Whatever "reasonable" model of computation one adopts, the class of polynomial-time solvable problems remains the same.

P sits at the bottom of the complexity hierarchy: P ⊆ NP ⊆ PSPACE. It is conjectured — but unproven — that all these containments are strict. If P = NP, the entire edifice of computational cryptography collapses, and problems currently considered intractable become routine. The class P is therefore not merely a mathematical object but a claim about the structure of solvability itself: it marks the boundary between problems that yield to systematic search and problems that resist it.