The Class P
P is the class of decision problems solvable by a deterministic algorithm in time polynomial in the input size.
Definition
P (polynomial time) contains every decision problem for which some algorithm runs in O(n^k) time for a fixed constant k, where n is the input size. These are the problems we can solve outright, not just check, within a reasonable scaling of effort.
Why polynomial is the line
Polynomial time is the standard formalization of tractable. Polynomials are closed under addition, multiplication, and composition, so building algorithms out of polynomial pieces keeps the result polynomial. Exponential time, by contrast, explodes so fast that even modest inputs become hopeless.
Examples in P
- Sorting a list
- Shortest paths in a graph (Dijkstra)
- Testing whether a number is prime
- Linear programming
- Matching in bipartite graphs
Robustness of the class
P is remarkably stable across models of computation. Whether you use a single-tape or multi-tape Turing machine, a random-access machine, or a typical programming language, the class of polynomial-time problems is the same, up to polynomial changes in the exponent. This robustness is why P is treated as a fundamental object.
P versus NP
Every problem in P is also in NP, because a fast solver can also verify. The open question of whether P equals NP asks whether every efficiently checkable problem is also efficiently solvable. Most researchers believe the answer is no, but no proof exists.
The caveat about constants
Membership in P does not guarantee practicality. An O(n^100) algorithm is polynomial yet useless in practice. In reality, most natural problems in P have small exponents, so the class is a good, if imperfect, proxy for what can actually be computed at scale.