The classes DTIME, NTIME, DSPACE, and NSPACE

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

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.