此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2015年9月16日) 請邀請適合的人士改善本條目。更多的細節與詳情請參見討論頁。 |
此條目需要擴充。 (2015年9月16日) 請協助改善這篇條目,更進一步的訊息可能會在討論頁或擴充請求中找到。請在擴充條目後將此模板移除。 |
在計算複雜性理論裏面,複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。 NP這個有名的複雜度類,可以用NTIME來定義如下:
相同的,NEXPTIME這個複雜度類是由NTIME定義出來的,非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。
P ≟ NP | 這是一篇關於計算理論的小作品。您可以透過編輯或修訂擴充其內容。 |