Differences
This shows you the differences between two versions of the page.
dtime [2014/02/18 17:58] nikolaj |
dtime [2014/03/21 11:11] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ===== DTIME ===== | ||
- | ==== Set ==== | ||
- | | @#88DDEE: $ T:\mathbb N\to\mathbb N $| | ||
- | | @#FFBB00: $ L\in \mathrm{\bf{DTIME}}(T(n)) $ | | ||
- | |||
- | | @#AAFFAA: $ L\subseteq\{0,1\}^* $ | | ||
- | |||
- | | @#DDDDDD: $M\in\mathrm{TM}$ | | ||
- | | @#DDDDDD: $c\in\mathbb{N}$ | | ||
- | |||
- | | @#55EE55: $\exists M,c.\ M$ decides $L$ in $c\cdot T(n)$-time | | ||
- | |||
- | ==== Discussion ==== | ||
- | The ${\bf{D}}$ stands for deterministic. | ||
- | ==== Parents ==== | ||
- | === Requirements === | ||
- | [[Turing machine as partial function]] | ||
- | === Subset of === | ||
- | [[Bit string]] |