非確定性時間層譜定理

非確定性時間層譜定理（non-deterministic time hierarchy theorem）是2018年公布的計算機科學技術名詞。

基本介紹

• 中文名：非確定性時間層譜定理
• 外文名：non-deterministic time hierarchy theorem
• 所屬學科：計算機科學技術
• 公布時間：2018年

定義

如果 f,g 都是時間可構造函式且 f ( n +1)= o(g(n)) ，那么，NTIME( f(n) )NTIME( g(n) )，這裡NTIME( f(n) )是非確定型圖靈機在時間 f(n) 內所識別的一切語言構成的類。

出處

《計算機科學技術名詞 》 (第三版)。