Time Complexity & the Class P

the limits of identifying P with feasible

Equating the class P with 'feasible' is the best simple rule complexity theory has, and it is right far more often than it is wrong. But a rule worth using is a rule worth questioning, and a careful student should hold the equation as a useful idealisation rather than a literal truth. The picture to keep is a map drawn at the scale of a continent: superb for seeing that polynomial and exponential are different countries, but too coarse to tell you whether a particular town has a good road.

The equation fails in two opposite directions. In one direction, being in P does not guarantee a usable algorithm. A running time of n^100, or of c times n for a constant c equal to 10^40, is polynomial by definition yet could not finish on any input in the lifetime of the universe; theorists call these galactic algorithms, polynomial in name only. In the other direction, being outside P (or worst-case intractable) does not guarantee uselessness. Worst-case analysis can be wildly pessimistic: the simplex method for linear programming is exponential in the worst case yet superb in practice, and many NP-hard problems are routinely solved on real instances by heuristics, approximation, or because typical inputs are far easier than the worst. Average-case behaviour can diverge from worst-case entirely.

None of this dethrones P; it locates it honestly. P remains the standard, model-independent, composition-friendly definition of efficient, the right default and the right teaching line, precisely because the alternatives are messier and less robust. The discipline is simply to remember what kind of statement 'P equals feasible' is: a sharp, provable, asymptotic idealisation that captures the polynomial-versus-exponential canyon, not a promise about the constant in front, the size of the exponent, or how a given algorithm behaves on the inputs you actually meet. Understood that way, P is a tool you wield, not an idol you worship.

An algorithm running in n^100 time is in P, yet for n = 10 it would take 10^100 steps, more than the number of atoms in the universe: polynomial, but a galactic algorithm. Conversely, the simplex method is worst-case exponential but solves real linear programs with millions of variables in moments. P captures neither nuance; it captures only the polynomial-versus-exponential divide.

P captures the polynomial-versus-exponential divide, not the constant, the exponent's size, or typical-case behaviour.

P is the standard idealisation of 'feasible', not a literal synonym: an n^100 or huge-constant algorithm is in P yet useless, and a worst-case-hard problem can be easy on the inputs that actually arise. Use P as a tool, not an idol.

Also called
P is not exactly feasibilitycaveats of P as efficientgalactic algorithmsP 等於可行的警告