Time Complexity and the Class P

Core Idea

The time complexity of a Turing machine on an input is the number of steps before it halts. DTIME(f(n)) is the class of languages decidable in O(f(n)) steps. The class P = ∪ₖ DTIME(nᵏ) captures 'efficiently solvable' problems — those with polynomial-time algorithms. P is robust to reasonable changes in the computational model (multi-tape TMs, random-access machines), making it the standard definition of tractability. The linear speedup theorem shows that constant factors in time bounds are irrelevant for class membership.

How It's Best Learned

Work through concrete examples of problems in P: sorting, graph reachability, primality testing (AKS). Then practice proving time bounds by counting TM steps or reasoning about algorithm complexity. Understand why polynomial vs. super-polynomial is the key dividing line rather than, say, linear vs. quadratic.

Common Misconceptions

• P is not the same as 'fast in practice' — a polynomial algorithm with exponent 100 is theoretically tractable but useless for real inputs.
• The robustness of P across models does not extend to all complexity classes; finer classes like NC or L are sensitive to model choice.

Explainer

A Turing machine's time complexity on input x is simply the number of steps it takes before halting. To talk about complexity classes, we shift from individual inputs to languages: DTIME(f(n)) is the set of all languages that some deterministic Turing machine decides within O(f(n)) steps on every input of length n. This gives us a hierarchy — DTIME(n) ⊂ DTIME(n²) ⊂ DTIME(n³) ⊂ ... — and the class P is defined as the union of all these polynomial classes.

Why the union over *all* polynomials, rather than picking a specific one like quadratic? The answer is closure. If you run a cubic-time algorithm and then feed its output into a quadratic-time algorithm, the composition is still polynomial — but it might be degree 5 or 6, not 2 or 3. By defining P as the union over all finite-degree polynomials, we get a class that is closed under composition: any algorithm built from P-subroutines is itself in P. This composability is what makes P a natural unit for reasoning about tractable computation, not just an arbitrary choice.

The robustness of P is equally important. A polynomial-time algorithm on a single-tape Turing machine can be simulated on a multi-tape Turing machine, on a random-access machine, or on most other reasonable deterministic models, with at most polynomial overhead. The polynomial-versus-super-polynomial divide therefore does not depend on the specific machine model you choose — it is a property of the problem, not of the hardware abstraction. This is why P is used as the formal definition of "efficiently solvable" rather than something like "linear-tape TM in quadratic time."

The linear speedup theorem reinforces this picture: for any c > 1, any language in DTIME(f(n)) is also in DTIME(f(n)/c). This means constant factors in time bounds are irrelevant for class membership — they wash out under rescaling. What matters for P membership is whether the growth rate is bounded by some polynomial, not the specific constants or low-degree polynomial exponent involved.

One critical misconception to resist: P is not "efficiently solvable in practice." An algorithm running in n⁵⁰ steps is in P but completely unusable. P is a theoretical lower bound on the possibility of tractability — if a problem is not in P, we have strong evidence it is fundamentally hard, regardless of hardware or clever implementation. If it is in P, we know tractability is possible in principle, but practical efficiency requires looking at specific exponents, average-case behavior, and constant factors that the asymptotic P definition deliberately ignores.