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}}$

クラス ELEMENTARY に属す関数は初等帰納的（しょとうきのうてき、英: elementary recursive）あるいは単に初等的と呼ばれる。この名称はカルマールによる造語である。

帰納的関数や決定不能性の文脈で扱われる多くの問題は ELEMENTARY よりも高いレベルにある。いくつかの帰納的問題は ELEMENTARY を超える。すなわち NONELEMENTARY となる。とくに注目されるのは、原始帰納的問題で ELEMENTARY に属さないものが存在することである。次が知られている。

LOWER-ELEMENTARY $\subsetneq$ EXPTIME $\subsetneq$ ELEMENTARY $\subsetneq$ PR $\subsetneq$ R

ELEMENTARY は指数関数の定数回の入れ子（例えば $2^{2^{n}}$）を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの（例えばテトレーション）を含む。

定義と例

初等帰納的関数の定義は原始帰納を限定和と限定積に置き換わっている点を除けば原始帰納的関数と同様に定義される。（通常、減算は原始帰納的関数の基本関数に含めないが、原始帰納的である。）全ての関数は自然数に対して作用するものとする。基本関数は次のものからなる：

1. ゼロ関数： $Z({\overrightarrow {x}})=0$
2. 後者関数： $S(x)=x+1$
3. 射影関数: $P_{\mu }^{\nu }({\overrightarrow {x}})=x_{\mu }$
4. 減算関数: $x{\dot {-}}y={\begin{cases}x-y&{\mbox{if }}x\geq y\\0&{\mbox{otherwise}}\end{cases}}$

これらの基本関数に次の基本構成を繰り返して得られる関数が初等帰納的関数である：

1. 合成: $h({\overrightarrow {x}})=f(g_{1}({\overrightarrow {x}}),g_{2}({\overrightarrow {x}}),\ldots ,g_{\mu }({\overrightarrow {x}}))$
2. 限定和: $f({\overrightarrow {x}},y)=\sum \limits _{z<y}g({\overrightarrow {x}},z)$
3. 限定積: $f({\overrightarrow {x}},y)=\prod \limits _{z<y}g({\overrightarrow {x}},z)$

初等的関数の例としては次のものがある：

乗算関数： $x\cdot y=\sum \limits _{z<y}x$

加算関数： $x+y=S(x)\cdot S(y){\dot {-}}S(x\cdot y)$

冪乗関数： $x^{y}=\prod \limits _{z<y}x$

素数列： $p_{n}=2,3,5,7,11,\ldots$

性質

初等的関数は限定原始再帰で閉じている。すなわち g, h と j が初等的であり

$f(t,{\bar {u}})\leq j(t,{\bar {u}})$

$f(0,{\bar {u}})=g({\bar {u}})$

$f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))$

ならば、 f もまた初等的である。

初等的関数は次の何れかの関数で支配される。すなわち任意の初等的関数は次に挙げる関数の何れかより小さい：

$x,2^{x},2^{2^{x}},2^{2^{2^{x}}},\ldots$

このリストを枚挙する原始帰納的関数 $f(c,x)=\underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}$ は初等的でない：対角線論法による。$f(c,x)$ が初等的と仮定する。すると $f(x,x)$ もまた初等的であるから、ある c に対して $f(x,x)<f(c,x)$ が成り立つ。ところがここで $x=c$ とすると不合理を得る。同様の増大度を持つテトレーションもまた初等的でない原始帰納的関数である。

クラス ELEMENTARY はレベル3のグジェゴルチク階層、深さ2のループプログラムで計算可能な関数のクラス、時間計算量が指数関数の定数回の反復で抑えられる関数のクラスなどと一致する。

低初等帰納的関数

限定積を用いずに定義できる初等的関数は低初等帰納的（英: lower elementary recursive）という。すなわち、低初等帰納的関数はゼロ関数, 後者関数, 射影関数, 減算関数から始めて関数合成と限定和を取る操作を有限回繰り返して得られる関数をいう。低初等的関数のクラスを LOWER-ELEMENTARY と書く。スコーレムの初等関数としても知られる。

初等的関数が潜在的に指数的な増大度を持つが、他方で低初等的関数は多項式の増大度を持つ。すなわち低初等的関数は多項式関数で支配される。したがって指数関数は初等的だが低初等的でない。

これは初等関数における同様の結果のアナロジーとして、低初等的関数もまた幾つかの単純な関数の合成によって記述できる。すなわち、多項式で抑えられる関数が低初等的であるのは、それが次の関数の合成で表せるとき、かつそのときに限る：射影, $n+1$, $nm$, $n\,{\stackrel {.}{-}}\,m$, $n\wedge m$, $\lfloor n/m\rfloor$, 指数関数　($2^{n}$ または $n^{m}$) 。ただし二つ以上の指数関数の底を含まないものとする。例えば $xy(z+1)$ は底を1つ含み、$(x+y)^{yz+x}+z^{x+1}$ は2つ含み、$2^{2^{x}}$ は3つ含む。ここで $n\wedge m$ はビットごとのANDを表す。

ELEMENTARY の基底

初等的関数のクラスは次の何れかの集合と射影の合成に関する閉包と一致する： $\{n+1,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,n^{m}\}$, $\{n+m,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,2^{n}\}$, $\{n+m,n^{2},n{\bmod {m}},2^{n}\}$ ここで $n{\dot {-}}m=\max\{n-m,0\}$は上で定義した減算関数である。 したがって例えば素数列はこれらの関数と自由代入とを用いた表示を持つことになる。

記述的特徴付け

記述計算量の観点から見ると ELEMENTARY は 高階論理 で表されるクラスに一致する。 これの意味することは複雑性クラス ELEMENTARY に属す任意の言語は高階の論理式によって定義可能ということである。もっと正確にいえば $\mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists {}HO^{i}$ が成り立つ。ここで $\cdots$ は $i$ 個の指数のタワーを表す。また $\exists {}HO^{i}$ は $i$ 階の存在量化から始まり $i-1$ 階の論理式が続く形の論理式で表される問い合わせと一致する。

関連項目

• 初等関数算術
• 原始帰納的関数
• グジェゴルチク階層
• EXPTIME

References

• Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3