A language of finite binary strings belongs to $\mathrm{P}$ if a deterministic Turing machine decides membership in that language in polynomial time. Precisely, there are a single machine and a polynomial $p \in \mathbb{N}[X]$ such that, on every input $w$, the machine halts within $p(|w|)$ steps and returns the bit $1$ if $w$ belongs to the language and $0$ otherwise.

The definition uses mathlib's deterministic stack machines, the identity encoding of binary strings, and a singleton Boolean output. Time counts transitions of fixed finite instruction blocks. We also prove equivalence with elementary single-tape machines.

The finite-stack class requires every stack alphabet to be finite. The single-tape class uses a deterministic machine whose transitions each move the head one square or write one symbol. Its alphabet and control states are finite. The input is written in its original order, starting at the head, with blank tape elsewhere. The two input symbols are distinct and different from blank. A halted control state determines the Boolean answer; work tape need not be erased.

A binary language $A$ belongs to $\mathrm{NP}$ if there are a verifier language $V\in\mathrm{P}$ and a polynomial $p\in\mathbb{N}[X]$ such that $x\in A$ precisely when some binary certificate $y$ with $|y|\le p(|x|)$ satisfies $\langle x,y\rangle\in V$. The verifier is a single deterministic polynomial-time decider on the explicit pair encoding, and its running time is polynomial in the combined input and certificate lengths. The certificate bound depends only on the original input length. This is the standard certificate definition of NP.

A machine has finitely many control states, a finite work alphabet with a blank symbol, a read-only binary input tape between distinct endmarkers, and one initially blank, semi-infinite work tape. Both heads start at position zero, which is the input's left endmarker and the work tape's leftmost cell. One transition reads the two scanned symbols, writes one work symbol, changes state, and moves each head by at most one cell. An outward move at a tape boundary leaves that head in place.

The finite transition table gives a finite set of possible actions for each state and pair of scanned symbols. A deterministic machine has at most one action in every such set. A configuration with no successor is terminal, and its control state supplies an accept/reject bit. Acceptance means that some computation branch reaches an accepting terminal configuration. A decider has a finite bound on the lengths of all branches for each input, and accepts exactly the strings in its language. This bound need not be computable or satisfy any specified time bound.

Only the work tape is charged as space. Bounding its head below $s$ at every reachable configuration bounds every visited cell to the prefix $0,\ldots,s-1$, including blank cells and cells later erased. The input head is confined to $|x|+2$ positions and cannot act as an unbounded free counter. The transition table sees neither head position nor the input length; it sees only the control state and scanned symbols.

For a function $s:\mathbb{N}\to\mathbb{N}$, the classes DSPACE and NSPACE below use the exact bound $s(n)$ on the number of work cells visited. There is one machine for all inputs, it halts on every branch, and every reachable configuration on an input of length $n$ respects the bound. DSPACE additionally requires deterministic transitions. Constant factors are quantified explicitly when the classical space classes are defined. We use $\lfloor\log_2(n+2)\rfloor$ as a positive logarithmic bound, so empty inputs are included without a special case.

A binary language belongs to $\mathrm{L}$ if a deterministic Turing machine decides membership using $O(\log n)$ work space and a separate read-only input tape. Precisely, some positive constant $c$ bounds work space by $c\lfloor\log_2(n+2)\rfloor$ on every input of length $n$.

A binary language belongs to $\mathrm{NL}$ if a nondeterministic Turing machine decides membership using $O(\log n)$ work space and a separate read-only input tape. Every branch halts and respects the space bound; membership means that at least one branch accepts. The bound is $c\lfloor\log_2(n+2)\rfloor$ for one positive constant $c$.

A binary language belongs to $\mathrm{PSPACE}$ if one deterministic Turing machine decides membership using at most $p(n)$ work cells on inputs of length $n$, for some polynomial $p\in\mathbb{N}[X]$. The input tape is read-only and excluded from work space, and the machine always halts.

A binary language belongs to $\mathrm{NPSPACE}$ if one nondeterministic Turing machine decides membership using at most $p(n)$ work cells on every branch on inputs of length $n$, for some polynomial $p\in\mathbb{N}[X]$. All branches halt; at least one accepts precisely when the input belongs to the language. The input tape is read-only and excluded from work space.

For a class $\mathcal C$ of binary languages, $\mathrm{co}\mathcal C$ consists of languages whose complements belong to $\mathcal C$. Complements are taken among all finite binary strings. In particular, $A\in\mathrm{coNL}$ means $\overline A\in\mathrm{NL}$, and $A\in\mathrm{coNP}$ means $\overline A\in\mathrm{NP}$. This operation complements each language; it does not take the set-theoretic complement of the class of languages.

A binary language belongs to $\mathrm{EXPTIME}$ if a deterministic Turing machine decides membership within $2^{p(n)}$ transitions on every input of length $n$, for some polynomial $p\in\mathbb{N}[X]$. The machine is the finite elementary single-tape machine defined here: input bits are distinct from blank, input appears in its original order, and each transition performs one move or one write. A terminal state's Boolean label gives the answer. The polynomial in the exponent may have any fixed degree; this is the usual EXPTIME, also called EXP.