跳转到内容

ELEMENTARY

维基百科,自由的百科全书

计算复杂度理论里面,复杂度类ELEMENTARY是所有指数谱系里面的复杂度类联集:

这名称最早是为了探讨可计算函数不可判定问题,由László Kalmár所提出;most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY。相当值得注意的,有一些原始递归函数问题不在ELEMENTARY内。我们已知:

LOWER-ELEMENTARY EXPTIME ELEMENTARY PR

与ELEMENTARY仅包含有限的(例如,)比较,PR使用的 超运算更一般化(例如,tetration),因此PR不包含于ELEMENTARY。