ELEMENTARYのソースを表示

{{Otheruses|複雑性クラス|Linuxディストリビューション|elementary OS}}
[[計算複雑性理論]]において '''ELEMENTARY''' とは{{仮リンク|指数階層|en|Exponential hierarchy}}の和集合で表される[[複雑性クラス]]である。

: <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>

クラス ELEMENTARY に属す関数は初等帰納的（しょとうきのうてき、{{lang-en-short|elementary recursive}}）あるいは単に初等的と呼ばれる。この名称は{{仮リンク|カルマール|en|László Kalmár}}による造語である。

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

:LOWER-ELEMENTARY <math>\subsetneq</math> [[EXPTIME]] <math>\subsetneq</math> ELEMENTARY <math>\subsetneq</math> [[PR_(計算複雑性理論)|PR]] <math>\subsetneq</math> [[R_(計算複雑性理論)|R]]

ELEMENTARY は[[指数関数]]の定数回の入れ子（例えば <math>2^{2^n}</math>）を含むが、[[PR_(計算複雑性理論)|PR]]は指数関数の一般化である[[ハイパー演算子]]で ELEMENTARY に属さないもの（例えば[[テトレーション]]）を含む。

==定義と例==

初等帰納的関数の定義は原始帰納を限定和と限定積に置き換わっている点を除けば[[原始帰納的関数]]と同様に定義される。（通常、減算は原始帰納的関数の基本関数に含めないが、原始帰納的である。）全ての関数は自然数に対して作用するものとする。基本関数は次のものからなる：
# '''ゼロ関数'''： <math> Z(\overrightarrow{x}) = 0</math>
# '''後者関数'''： <math> S(x) = x + 1 </math>
# '''射影関数''': <math> P^{\nu}_{\mu}(\overrightarrow{x}) = x_{\mu} </math>
# '''減算関数''': <math>x \dot{-} y = \begin{cases}  x - y & \mbox{if }x \geq y \\ 0 & \mbox{otherwise} \end{cases} </math>

これらの基本関数に次の基本構成を繰り返して得られる関数が初等帰納的関数である：
# '''合成''': <math>h(\overrightarrow{x}) = f(g_1(\overrightarrow{x}),g_2(\overrightarrow{x}),\ldots,g_{\mu}(\overrightarrow{x}))</math>
# '''限定和''': <math>f(\overrightarrow{x}, y) = \sum\limits_{z<y} g(\overrightarrow{x}, z)</math>
# '''限定積''': <math>f(\overrightarrow{x}, y) = \prod\limits_{z<y} g(\overrightarrow{x}, z)</math>

初等的関数の例としては次のものがある：
: 乗算関数： <math>x \cdot y = \sum\limits_{z < y} x </math>
: 加算関数： <math> x + y = S(x) \cdot S(y) \dot{-} S(x \cdot y) </math>
: 冪乗関数： <math> x^y = \prod\limits_{z < y} x </math>
: [[素数]]列： <math> p_n = 2, 3, 5, 7, 11, \ldots</math>

== 性質 ==

初等的関数は限定原始再帰で閉じている。すなわち ''g'', ''h'' と ''j'' が初等的であり
:<math>f(t, \bar{u}) \leq j(t, \bar{u})</math>
:<math>f(0, \bar{u}) = g(\bar{u})</math>
:<math>f(t+1, \bar{u}) = h(t,\bar{u},f(t,\bar{u}))</math>
ならば、 ''f'' もまた初等的である。

初等的関数は次の何れかの関数で支配される。すなわち任意の初等的関数は次に挙げる関数の何れかより小さい：
: <math>x,2^x, 2^{2^x}, 2^{2^{2^x}}, \ldots </math>
このリストを枚挙する原始帰納的関数 <math>f(c, x) = \underbrace{2^{2^{\cdot^{\cdot^x}}}}_{c}</math> は初等的でない：[[対角線論法]]による。<math>f(c, x)</math> が初等的と仮定する。すると <math>f(x, x)</math> もまた初等的であるから、ある ''c'' に対して <math>f(x, x) < f(c, x)</math> が成り立つ。ところがここで <math>x = c</math> とすると不合理を得る。同様の増大度を持つ[[テトレーション]]もまた初等的でない原始帰納的関数である。

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

== 低初等帰納的関数 ==

限定積を用いずに定義できる初等的関数は'''低初等帰納的'''（{{lang-en-short|lower elementary recursive}}）という。すなわち、低初等帰納的関数はゼロ関数, 後者関数, 射影関数, 減算関数から始めて関数合成と限定和を取る操作を有限回繰り返して得られる関数をいう。低初等的関数のクラスを LOWER-ELEMENTARY と書く。スコーレムの初等関数としても知られる<ref>Th. Skolem, "Proof of some theorems on recursively enumerable sets", ''Notre Dame Journal of Formal Logic'', 1962, Volume 3, Number 2, pp 65-74, {{doi|10.1305/ndjfl/1093957149}}.</ref><ref name="volkov_skolem">S. A. Volkov, "On the class of Skolem elementary functions", ''Journal of Applied and Industrial Mathematics'', 2010, Volume 4, Issue 4, pp 588-599, {{doi|10.1134/S1990478910040149}}.</ref>。

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

これは初等関数における同様の結果のアナロジーとして、低初等的関数もまた幾つかの単純な関数の合成によって記述できる<ref name="volkov_skolem" /><ref>{{cite arXiv |last=Volkov |first=Sergey | year= 2016 |eprint=1611.04843 |title=Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation] }}</ref>。すなわち、多項式で抑えられる関数が低初等的であるのは、それが次の関数の合成で表せるとき、かつそのときに限る：射影, <math>n+1</math>, <math>nm</math>, <math>n \,\stackrel{.}{-}\, m</math>, <math>n\wedge m</math>, <math>\lfloor n/m \rfloor</math>, 指数関数　(<math>2^n</math> または <math>n^m</math>) 。ただし二つ以上の指数関数の底を含まないものとする。例えば <math>xy(z+1)</math> は底を1つ含み、<math>(x+y)^{yz+x}+z^{x+1}</math> は2つ含み、<math>2^{2^x}</math> は3つ含む。ここで <math>n\wedge m</math> はビットごとのANDを表す。

== ELEMENTARY の基底 ==

初等的関数のクラスは次の何れかの集合と射影の合成に関する閉包と一致する： <math>\{ n+1, n \stackrel{.}{-} m, \lfloor n/m \rfloor, n^{m} \}</math>, <math>\{ n+m, n \stackrel{.}{-} m, \lfloor n/m\rfloor, 2^{n} \}</math>, <math>\{ n+m, n^{2}, n \bmod m, 2^{n} \}</math> ここで <math>n \dot{-} m = \max\{n-m, 0\}</math>は上で定義した減算関数である。<ref>Mazzanti, S., "Plain Bases for Classes of Primitive Recursive Functions", Mathematical Logic Quarterly, 48 (2002) 93-104</ref> したがって例えば素数列はこれらの関数と自由代入とを用いた表示を持つことになる。

== 記述的特徴付け ==

[[記述計算量]]の観点から見ると ELEMENTARY は {{仮リンク|高階論理|en|HO (complexity)}} で表されるクラスに一致する。<ref>{{Citation | author = Lauri Hella and José María Turull-Torres | title =Computing queries with higher-order logics | journal =Theoretical Computer Science | volume = 355 | edition= (what is called "number" in bibtex) | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | publisher =Elsevier Science Publishers Ltd. | place =  Essex, UK | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009}}</ref> これの意味することは複雑性クラス ELEMENTARY に属す任意の言語は高階の論理式によって定義可能ということである。もっと正確にいえば <math>\mathrm{NTIME}(2^{2^{\cdots{2^{O(n)}}}}) = \exists{}HO^i</math> が成り立つ。ここで <math>\cdots</math> は <math>i</math> 個の指数のタワーを表す。また <math>\exists{}HO^i</math> は <math>i</math> 階の存在量化から始まり <math>i-1</math> 階の論理式が続く形の論理式で表される問い合わせと一致する。

== 関連項目 ==
* [[初等関数算術]]
* [[原始帰納的関数]]
* [[グジェゴルチク階層]]
* [[EXPTIME]]

== References ==
{{reflist}}
* Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3

{{複雑性クラス}}

{{DEFAULTSORT:えれめんたりい}}
[[Category:計算複雑性理論]]
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]