The classes DTIME, NTIME, DSPACE, and NSPACE

Let $t,s:\mathbb{N}\to \mathbb{N}$.

For nonnegative resource functions $a,b$, the notation $a(n)=O(b(n))$ means that some constants $c>0$ and $n_0$ satisfy $a(n)\le cb(n)$ for every $n\ge n_0$. Every resource bound below uses constants fixed for the machine, uniformly over all its inputs and branches. Time counts transitions; space counts all cells visited on all tapes, including the input tape, with each distinct tape/cell pair counted once. No constructibility assumption on $t$ or $s$ is needed to define these classes.

A language $L\subseteq {\mathrm{\Sigma }}^{\ast }$ belongs to DTIME$(t(n))$ when there exists a deterministic multitape Turing machine deciding $L$ in time $O(t(n))$.

A nondeterministic $k$-tape Turing machine is obtained from the deterministic $k$-tape model of Multitape and nondeterministic Turing machine variants by replacing its transition function with a finite-valued transition map ${\mathrm{\Delta }}_k:(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times {\mathrm{\Gamma }}^k⟶{\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(Q\times {\mathrm{\Gamma }}^k\times \{L,R{\}}^k)\mathrm{.}$ One branch chooses one instruction from the finite set at each step.

A language $L\subseteq {\mathrm{\Sigma }}^{\ast }$ belongs to NTIME$(t(n))$ when there exists such a nondeterministic $k$-tape machine $N$ for which:

• every branch of $N$ on every input of length $n$ halts within $O(t(n))$ steps, and
• some branch of $N$ accepts exactly on the words of $L$, in the same existential sense as Accepting computations of a nondeterministic machine.

A language $L\subseteq {\mathrm{\Sigma }}^{\ast }$ belongs to DSPACE$(s(n))$ when a deterministic multitape decider uses worst-case space $O(s(n))$. It belongs to NSPACE$(s(n))$ when a nondeterministic multitape machine accepts exactly the words in $L$, every branch halts, and the maximum number of visited cells over all branches and inputs of length $n$ is $O(s(n))$.

• These are language classes. Function classes are expressed separately by saying that a machine computing the function does so within a stated bound.

• The chosen machine model is multitape because it is convenient for programming; later theorems show that polynomial-time and polynomial-space notions do not depend on that choice.