Savitch's theorem

Savitch's theorem states that every problem solvable in nondeterministic space s(n) is solvable in deterministic space O(s(n)²), for space-constructible s(n) ≥ log n.

Configuration graph: A directed graph whose vertices represent machine configurations and whose edges represent legal transitions. A space-bounded computation becomes a path between configurations in this graph.
NPSPACE: The class of decision problems solvable by a nondeterministic Turing machine using polynomial space. Savitch's theorem places every problem in this class within deterministic polynomial space.
Nondeterministic Turing machine: A Turing machine that may have multiple possible next moves at each step. The theorem begins with computations that accept when at least one branch accepts.
Nondeterministic time: The running-time resource of a nondeterministic computation, measured by its longest computation branch. Savitch's theorem concerns space and does not give the same kind of quadratic simulation bound for time.
Bounded reachability: The problem of deciding whether a directed path of at most a specified length connects two vertices. Savitch's recursion asks whether configurations are connected by paths within a bounded number of steps.
PSPACE: The class of decision problems solvable by a deterministic Turing machine using polynomial space. The theorem implies NPSPACE equals PSPACE.
Turing machine configuration: A complete description of a Turing machine's state, tape contents, and head positions at one instant. A configuration records the information whose storage is bounded by the space assumption.
Savitch's theorem for time: A commonly stated but misleading name for a quadratic deterministic simulation of nondeterministic time. The established theorem is a space result; its recursive method may require much more time.
Recursive algorithm: An algorithm that solves a problem by invoking itself on smaller instances. The reachability test splits a path at a midpoint and recursively checks its two halves.
NL: The class of decision problems solvable by a nondeterministic Turing machine using logarithmic space. Applying the theorem to logarithmic space gives NL ⊆ DSPACE(log² n).

Linked from 2 pages