Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 59 ยท Complexity

Time Complexity and the Class P

Measure how many steps a Turing machine takes, define DTIME and the class P, see why input size matters, and run a Python machine that counts its own steps.

Up to now we asked a yes-or-no question: can a machine decide a language at all? The chapters on Turing machines and decidability showed that some languages are out of reach for every machine. But among the languages a machine can decide, some are easy and some are hopeless in practice. A machine that needs 10^30 steps to answer is technically a decider, yet nobody will ever see its answer.

Complexity theory replaces "can it be done?" with "how much does it cost?". The cost is measured in time (number of steps) and space (number of tape cells). In this lesson you learn how to count time on a Turing machine, how to group languages into classes by their running time, and why the class P is the standard formal stand-in for "efficiently solvable".

Counting steps

Fix a deterministic Turing machine M that halts on every input (a decider). For an input w, let steps(M, w) be the number of moves M makes before it halts. The running time of M is a function of the length of the input:

TEXT
t(n) = the largest steps(M, w) over all inputs w with |w| = n

This is a worst-case measure. We use the worst input of each length because we want a guarantee, not a lucky run. And we measure growth in terms of n, the number of input symbols, because an algorithm that takes 5 steps on a 3-symbol input tells us nothing about the 3,000-symbol input.

Because machine details (how many tapes, how the states are arranged) change the exact count, we almost always speak in asymptotic terms with big-O: t(n) = O(n^2) means the step count is bounded by a constant times n^2 for large n. The next demo shows a real machine growing quadratically.

Python A Turing machine that counts its own steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each round walks across the whole marked region and back, and there are n rounds. So the cost is about n times n, which is why the last column settles near a constant. This one-tape machine runs in O(n^2) time. A cleverer machine that crosses off half of the symbols per pass takes O(n log n), and that is the best possible for one tape.

DTIME and the class P

Now we group languages by cost. For a function t(n):

TEXT
DTIME(t(n)) = { L : some deterministic TM decides L in O(t(n)) steps }

So DTIME(n) contains the languages decidable in linear time, DTIME(n^2) those decidable in quadratic time, and so on. The central definition is the union over all polynomial bounds:

TEXT
P = DTIME(n^1) โˆช DTIME(n^2) โˆช DTIME(n^3) โˆช ... = โ‹ƒ_k DTIME(n^k)

A language is in P when some deterministic Turing machine decides it in polynomial time. Every regular language is in P (a DFA runs in n steps), every context-free language is in P (the CYK algorithm takes O(n^3)), and so are thousands of everyday problems: sorting, shortest paths, matching, linear programming, primality testing.

flowchart LR
    R["Regular languages<br/>O(n)"] --> C["Context-free languages<br/>O(n^3)"]
    C --> P["P<br/>polynomial time"]
    P --> D["Decidable languages"]
    D --> A["All languages"]

P sits inside the decidable languages, and it contains both regular and context-free languages.

Why polynomial?

Polynomial time is not a perfect model of "fast". A machine with running time n^100 is not practical, and one with 1.0001^n is fine for realistic n. We still draw the line at polynomials for three reasons:

  • Robustness. Any two reasonable deterministic models (multi-tape TMs, RAM machines, your laptop) simulate each other with only a polynomial slowdown. So "in P" does not depend on which model you pick. This is the extended Church-Turing thesis.
  • Closure. If you call a polynomial-time routine a polynomial number of times, or feed its output to another polynomial routine, you are still in polynomial time. P is closed under union, intersection, complement, concatenation and star.
  • Practice. Natural problems that turn out to be in P almost always have small exponents (n, n^2, n^3), and the gap between polynomial and exponential growth is enormous in practice.

Different tape counts change the exponent but not membership in P: a k-tape machine running in time t(n) can be simulated by a one-tape machine in O(t(n)^2). Moving from n to n^2 never leaves P.

Input size is everything

Complexity is measured against the length of the encoding of the input, not against the number the input represents. This trips up almost everyone the first time. Consider testing whether a number N is prime by trial division up to the square root of N. That is about sqrt(N) divisions, which looks cheap. But the input is written in binary with n = log2 N bits, so sqrt(N) = 2^(n/2): exponential in the input size. (Primality is in P, but only thanks to the cleverer AKS algorithm.)

Python Polynomial or exponential? It depends on the encoding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Adding 4 bits to the input multiplies the work by 4. That is exponential growth in the input length. The same warning applies to any problem with numbers: a unary encoding (the number 1000 written as 1000 ones) makes trial division polynomial, but nobody writes numbers that way. We always assume a reasonable encoding, such as binary, for numbers and an edge list or adjacency matrix for graphs.

Examples of problems in P

  • PATH: is there a path from s to t in a directed graph? Breadth-first search takes O(V + E) steps.
  • RELPRIME: are two numbers coprime? Euclid's algorithm takes O(n) divisions for n-bit numbers.
  • Context-free membership: is the string w generated by grammar G? The CYK algorithm runs in O(|w|^3).
  • 2-SAT: can a formula with clauses of two literals be satisfied? Solved through strongly connected components in linear time.

Notice what these share: a clever idea (a search order, a recurrence, a reduction to a graph) avoids trying every possibility. Problems that seem to need trying every possibility are the topic of the next lesson.

Common mistakes

  • Confusing the value of a number with its length. Complexity is a function of the number of bits.
  • Judging by one lucky input. Running time is the worst case over all inputs of length n.
  • Thinking "polynomial" means "practical". It means "scales sensibly as the problem grows".
  • Forgetting that every decider needs a step bound for every input; a machine that loops on some input does not decide anything, let alone in polynomial time.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the running time t(n) of a Turing machine measure?

    Running time is a worst-case measure taken over all inputs of length n, so it is a guarantee for every input of that size.
  2. 2. Which of these defines the class P?

    P is the union over all constants k of DTIME(n^k): deterministic polynomial time.
  3. 3. Trial division tests a b-bit number N for primality in about sqrt(N) steps. In terms of the input length b, this is

    sqrt(N) is about 2^(b/2), which is exponential in the number of bits b, the true input length.
  4. 4. A one-tape machine takes O(n^2) steps while a faster two-tape machine for the same language takes O(n). Is the language in P?

    Switching between reasonable models changes the exponent only by a polynomial factor, so membership in P does not change.

Summary

  • Running time is the worst-case step count as a function of input length n.
  • DTIME(t(n)) collects the languages decidable in O(t(n)) steps; P is the union of DTIME(n^k) over all k.
  • Polynomial time is robust across reasonable machine models and closed under composition.
  • Always measure against the length of the encoding, never the numeric value.
  • Regular and context-free languages are inside P.

Next: Nondeterminism and the Class NP