时间复杂度类

阐述

设 $t:\mathbb N\to\mathbb R^+$ ，定义时间复杂度类 $\operatorname{TIME}(t(n))$ 是所有能在 $O(t(n))$ 渐近时间内由某种确定性 Turing 机判别的语言的集合。

设 $t:\mathbb N\to\mathbb R^+$ ，定义时间复杂度类 $\operatorname{NTIME}(t(n))$ 是所有能在 $O(t(n))$ 渐近时间内由非确定性 Turing 机判别的语言的集合。