NTIME

在计算复杂性理论里面，复杂度类NTIME(f(n))是一种可以用非确定型图灵机使用O(f(n))的时间和无限制的空间所能解决的所有决定性问题的集合。 NP这个有名的复杂度类，可以用NTIME来定义如下：

{\mbox{NP}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(n^{k})

相同的，NEXPTIME这个复杂度类是由NTIME定义出来的，非决定型的时间谱系理论说明了非决定型的机器在使用更多时间的前提下可以解决更多的问题。

参考资料

P ≟ NP

这是一篇关于计算理论的小作品。您可以通过编辑或修订扩充其内容。