指数谱系

计算复杂性理论内,指数谱系是一个复杂度类的分类层级(hierarchy),以EXPTIME开始:

然后接着

,以下雷同。

我们已知P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …。跟相类似的多项式谱系不同,时间谱系理论(Time hierarchy theorem)保证了这列关系都是真子集(proper),意思是,存在语言在EXPTIME而不在P内,也存在语言在2-EXPTIME但不在EXPTIME内,以下类推。

将所有指数谱系的复杂度类作联集,我们会得到一个大的复杂度类,名为ELEMENTARY

参考资料

  • Computational Complexity. Addison Wesley, 1994. (pp 497-498)