NTIME

在計算複雜性理論裡面，複雜度類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
  • 查
  • 论
  • 编
易解复杂度类
对数空间相关
  • DLOGTIME
  • AC0（英语：AC0）
  • ACC0（英语：ACC0）
  • TC0（英语：TC0）
  • L · FL · SL · NL
  • NC
  • SC
  • PolyL
多项式空间相关
  • P（P-完全）
  • FP（英语：FP (complexity)）
  • ZPP
  • RP
  • BPP
  • BQP（QMA（英语：QMA）
  • PostBQP（英语：PostBQP）
  • EQP（英语：EQP））
P、NP、反NP与PSPACE之间的关系
怀疑难解复杂度类
  • UP
  • NP（NP完全
  • NP困难
  • 反NP
  • 反NP完全（英语：co-NP-complete））
  • FNP（英语：FNP (complexity)）（TFNP（英语：TFNP (complexity)））
  • PH
  • PP
  • #P（#P-完全（英语：Sharp-P-complete））
  • PSPACE（PSPACE完全（英语：PSPACE-complete））
难解复杂度类
复杂度类的谱系
相关复杂度族
P ≟ NP 这是一篇关于计算理论的小作品。您可以通过编辑或修订扩充其内容。
  • 查
  • 论
  • 编