查看“︁ELEMENTARY”︁的源代码

在[[計算複雜度理論]]裡面，[[複雜度類]]'''ELEMENTARY'''是所有[[指數譜系]]裡面的複雜度類聯集：

: <math> \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}
</math>

這名稱最早是為了探討[[可計算函數]]和[[不可判定問題]]，由[[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 <math>\subsetneq</math> [[EXPTIME]] <math>\subsetneq</math> ELEMENTARY <math>\subsetneq</math> [[PR (complexity)|PR]]

與ELEMENTARY僅包含有限的[[冪]]（例如，<math>O(2^{2^n})</math>）比較，[[PR (複雜度)|PR]]使用的 [[超運算]]更一般化（例如，[[tetration]]），因此PR不包含於ELEMENTARY。
<!--
== 定義 ==

The definitions of elementary recursive functions are the same as for [[原始遞歸函數]]s, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are:

# '''Zero function'''.  Returns zero: ''f''(x) = 0.
# '''Successor function''': ''f''(''x'') = ''x'' + 1. Often this is denoted by ''S'', as in ''S''(''x''). Via repeated application of a successor function, one can achieve addition.
# '''Projection functions''': these are used for ignoring arguments. For example, ''f''(''a'', ''b'') = ''a'' is a projection function.
# '''Subtraction function''': ''f''(''x'', ''y'') = ''x'' - ''y'' if ''y'' < ''x'', or 0 if ''y'' &ge; ''x''. This function is used to define conditionals and iteration.

From these basic functions, we can build other elementary recursive functions.

# '''Composition''': applying values from some elementary recursive function as an argument to another elementary recursive function. In ''f''(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>) = ''h''(''g''<sub>1</sub>(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>), ..., ''g''<sub>m</sub>(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>)) is elementary recursive if ''h'' is elementary recursive and each ''g''<sub>i</sub> is elementary recursive.
# '''Bounded summation''': <math>f(m, x_1, \ldots, x_n) = \sum\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> is elementary recursive if ''g'' is elementary recursive.
# '''Bounded product''': <math>f(m, x_1, \ldots, x_n) = \prod\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> is elementary recursive if ''g'' is elementary recursive.
-->

{{ComplexityClasses}}

[[Category:複雜度類]]