Time and Space Complexity Classes

Complexity classes group decision problems by the time or memory a machine needs to solve them, organizing computation into a structured landscape from logarithmic space up through exponential time.

Definition

A complexity class is the set of problems solvable within a stated bound on a resource, typically the time or the working memory used by a Turing machine as a function of input length, with deterministic and nondeterministic variants for each resource.

Scope

This topic covers the definition of deterministic and nondeterministic time and space classes such as P, NP, L, NL, PSPACE, and EXPTIME, the hierarchy theorems that separate them, inclusions and known relationships among them, Savitch's theorem relating nondeterministic and deterministic space, and the complete problems that characterize each class.

Core questions

• How are problems grouped by the time and memory their solution requires?
• Which inclusions among the standard complexity classes are known to be strict?
• How does nondeterministic space relate to deterministic space?
• What role do complete problems play in characterizing a class?

Key theories

Hierarchy theorems

With asymptotically more time or space a machine can decide strictly more languages, so the time and space classes form proper hierarchies and resources cannot be wasted without losing problems.

Savitch's theorem

Any problem solvable in nondeterministic space can be solved deterministically using only the square of that space, so for memory, unlike apparently for time, nondeterminism provides at most a modest advantage.

Clinical relevance

Placing a problem in a complexity class tells practitioners what to expect: problems in P scale to large inputs, PSPACE-complete problems such as many games and planning tasks resist efficient solution, and the class structure guides whether to seek exact algorithms, approximations, or to redesign the problem.

History

Hartmanis and Stearns defined time-bounded classes and proved the time hierarchy theorem in 1965, founding the field. Space complexity was developed in parallel, with Savitch's 1970 theorem and later results such as Immerman and Szelepcsényi's closure of nondeterministic space under complement refining the picture.

Key figures

• Juris Hartmanis
• Richard Stearns
• Walter Savitch
• Stephen Cook

Seminal works

• hartmanisStearns1965
• savitch1970

Frequently asked questions

What is the difference between time and space complexity?

Time complexity counts the number of steps an algorithm takes, while space complexity measures the working memory it uses. They behave differently: space can be reused as a computation proceeds, which is why nondeterministic space is far less powerful relative to deterministic space than the analogous comparison for time appears to be.

Why do hierarchy theorems matter?

They prove that more resources genuinely allow more problems to be solved, ruling out the possibility that all classes collapse into one. This guarantees, for example, that there are problems solvable in exponential time but not in polynomial time, anchoring the whole edifice of complexity classes.