Time Complexity & the Class P

a time-complexity class

Once we can measure how long a machine takes, the natural next move is to sort problems into bins by how much time they need. A time-complexity class is exactly such a bin: a collection of all the decision problems (languages) that some machine can decide within a stated time budget. Instead of asking about one algorithm, we ask about a whole population of problems and draw boundaries around what is solvable inside a given amount of time.

The basic building block is written TIME(f(n)), sometimes DTIME(f(n)) to stress 'deterministic'. A language L is in TIME(f(n)) if there is a deterministic Turing machine that decides L (halts with the right yes/no answer on every input) and, on every input of size n, halts within O(f(n)) steps. So TIME(n^2) is all problems solvable in quadratic time, TIME(2^n) all problems solvable in exponential time, and so on. We use O(f(n)) inside the definition so the class does not depend on petty constant factors. These classes nest: a problem solvable in n time is certainly solvable in n^2 time, so TIME(n) is contained in TIME(n^2).

Single classes like TIME(n^3) are sensitive to the exact bound and even to the machine model, which is why the most useful classes are unions that smooth those wrinkles away. The star example is P, the union of TIME(n^k) over all constants k, gathering everything solvable in any polynomial time. Bundling like this makes the class robust across reasonable models and gives us stable landmarks (P, EXPTIME, and later PSPACE) on the map of computation. The time hierarchy theorem then guarantees that genuinely more time buys genuinely more power, so these bins are not all secretly equal.

Sorting n numbers by comparisons is in TIME(n^2) (a simple bubble sort) and even in TIME(n log n) (merge sort), hence in P. Deciding a hard search by trying all subsets sits in TIME(2^n), part of EXPTIME. The classes nest: every problem in TIME(n log n) is also in TIME(n^2), which is inside P, which is inside EXPTIME.

TIME(f(n)) bins problems by their time budget; unions like P bundle many bins into a robust landmark.

TIME(f(n)) is defined with a deterministic machine and an O(f(n)) step bound; a single bound is model-sensitive, which is why the durable classes (notably P) are unions over a whole family of bounds.

Also called
TIME(f(n))DTIME(f(n))time-bounded classdeterministic time class時間類別