NTIME此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (2015年9月16日)请邀请适合的人士改善本条目。更多的细节与详情请参见讨论页。此条目需要扩充。 (2015年9月16日)请协助改善这篇条目,更进一步的信息可能会在讨论页或扩充请求中找到。请在扩充条目后将此模板移除。在计算复杂性理论里面,复杂度类NTIME(f(n))是一种可以用非确定型图灵机使用O(f(n))的时间和无限制的空间所能解决的所有决定性问题的集合。 NP这个有名的复杂度类,可以用NTIME来定义如下: NP = ⋃ k ∈ N NTIME ( n k ) {\displaystyle {\mbox{NP}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(n^{k})} 相同的,NEXPTIME这个复杂度类是由NTIME定义出来的,非决定型的时间谱系理论说明了非决定型的机器在使用更多时间的前提下可以解决更多的问题。 参考资料 (英文)Complexity Zoo: NTIME