ELEMENTARY

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜度理論裡面,複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集:

 \begin{matrix}
  \mathrm{ELEMENTARY}  & = & \mathrm{EXP}\cup\mathrm{2EXP}\cup\mathrm{3EXP}\cup\cdots \\
                   & = & \mathrm{DTIME}(2^{n})\cup\mathrm{DTIME}(2^{2^{n}})\cup
                         \mathrm{DTIME}(2^{2^{2^{n}}})\cup\cdots
  \end{matrix}

這名稱最早是為了探討可計算函數不可判定問題,由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 \subsetneq EXPTIME \subsetneq ELEMENTARY \subsetneq PR

與ELEMENTARY僅包含有限的(例如,O(2^{2^n}))比較,PR使用的 超運算更一般化(例如,tetration),因此PR不包含於ELEMENTARY。