This is an old revision of the document!
DTIME
Set
$ T:\mathbb N\to\mathbb N $ |
$ L\in \mathrm{\bf{DTIME}}(T(n)) $ |
$ L\subseteq\{0,1\}^* $ |
$M\in\mathrm{TM}$ |
$c\in\mathbb{N}$ |
$\exists M,c.\ M$ decides $L$ in $c\cdot T(n)$-time |
Discussion
The {\bf{D}} stands for deterministic.