非确定性时间层谱定理

（计算机科学技术）

非确定性时间层谱定理（non-deterministic time hierarchy theorem），计算机科学技术名词，如果 f，g 都是时间可构造函数且 f ( n +1)= o(g(n)) ，那么，NTIME( f(n) )NTIME( g(n) )，这里NTIME( f(n) )是非确定型图灵机在时间 f(n) 内所识别的一切语言构成的类。