この項目では、複雑性クラスについて説明しています。Linuxディストリビューションについては「elementary OS 」をご覧ください。
計算複雑性理論 において ELEMENTARY とは指数階層（英語版 ） の和集合で表される複雑性クラス である。
E
L
E
M
E
N
T
A
R
Y
=
E
X
P
∪
2
E
X
P
∪
3
E
X
P
∪
⋯
=
D
T
I
M
E
(
2
n
)
∪
D
T
I
M
E
(
2
2
n
)
∪
D
T
I
M
E
(
2
2
2
n
)
∪
⋯
{\displaystyle {\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
⊊
{\displaystyle \subsetneq }
EXPTIME
⊊
{\displaystyle \subsetneq }
⊊
{\displaystyle \subsetneq }
PR
⊊
{\displaystyle \subsetneq }
R
ELEMENTARY は指数関数 の定数回の入れ子（例えば
2
2
n
{\displaystyle 2^{2^{n}}}
PR は指数関数の一般化であるハイパー演算子 で ELEMENTARY に属さないもの（例えばテトレーション ）を含む。
定義と例 初等帰納的関数の定義は原始帰納を限定和と限定積に置き換わっている点を除けば原始帰納的関数 と同様に定義される。（通常、減算は原始帰納的関数の基本関数に含めないが、原始帰納的である。）全ての関数は自然数に対して作用するものとする。基本関数は次のものからなる：
ゼロ関数 ：
Z
(
x
→
)
=
0
{\displaystyle Z({\overrightarrow {x}})=0}
後者関数 ：
S
(
x
)
=
x
+
1
{\displaystyle S(x)=x+1}
射影関数 :
P
μ
ν
(
x
→
)
=
x
μ
{\displaystyle P_{\mu }^{\nu }({\overrightarrow {x}})=x_{\mu }}
減算関数 :
x
−
˙
y
=
{
x
−
y
if
x
≥
y
0
otherwise
{\displaystyle x{\dot {-}}y={\begin{cases}x-y&{\mbox{if }}x\geq y\\0&{\mbox{otherwise}}\end{cases}}}
これらの基本関数に次の基本構成を繰り返して得られる関数が初等帰納的関数である：
合成 :
h
(
x
→
)
=
f
(
g
1
(
x
→
)
,
g
2
(
x
→
)
,
…
,
g
μ
(
x
→
)
)
{\displaystyle h({\overrightarrow {x}})=f(g_{1}({\overrightarrow {x}}),g_{2}({\overrightarrow {x}}),\ldots ,g_{\mu }({\overrightarrow {x}}))}
限定和 :
f
(
x
→
,
y
)
=
∑
z
<
y
g
(
x
→
,
z
)
{\displaystyle f({\overrightarrow {x}},y)=\sum \limits _{z<y}g({\overrightarrow {x}},z)}
限定積 :
f
(
x
→
,
y
)
=
∏
z
<
y
g
(
x
→
,
z
)
{\displaystyle f({\overrightarrow {x}},y)=\prod \limits _{z<y}g({\overrightarrow {x}},z)}
初等的関数の例としては次のものがある：
乗算関数：
x
⋅
y
=
∑
z
<
y
x
{\displaystyle x\cdot y=\sum \limits _{z<y}x}
加算関数：
x
+
y
=
S
(
x
)
⋅
S
(
y
)
−
˙
S
(
x
⋅
y
)
{\displaystyle x+y=S(x)\cdot S(y){\dot {-}}S(x\cdot y)}
冪乗関数：
x
y
=
∏
z
<
y
x
{\displaystyle x^{y}=\prod \limits _{z<y}x}
素数 列：
p
n
=
2
,
3
,
5
,
7
,
11
,
…
{\displaystyle p_{n}=2,3,5,7,11,\ldots }
性質 初等的関数は限定原始再帰で閉じている。すなわち g , h と j が初等的であり
f
(
t
,
u
¯
)
≤
j
(
t
,
u
¯
)
{\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}
f
(
0
,
u
¯
)
=
g
(
u
¯
)
{\displaystyle f(0,{\bar {u}})=g({\bar {u}})}
f
(
t
+
1
,
u
¯
)
=
h
(
t
,
u
¯
,
f
(
t
,
u
¯
)
)
{\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}
ならば、 f もまた初等的である。
初等的関数は次の何れかの関数で支配される。すなわち任意の初等的関数は次に挙げる関数の何れかより小さい：
x
,
2
x
,
2
2
x
,
2
2
2
x
,
…
{\displaystyle x,2^{x},2^{2^{x}},2^{2^{2^{x}}},\ldots }
このリストを枚挙する原始帰納的関数
f
(
c
,
x
)
=
2
2
⋅
⋅
x
⏟
c
{\displaystyle f(c,x)=\underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}}
対角線論法 による。
f
(
c
,
x
)
{\displaystyle f(c,x)}
f
(
x
,
x
)
{\displaystyle f(x,x)}
c に対して
f
(
x
,
x
)
<
f
(
c
,
x
)
{\displaystyle f(x,x)<f(c,x)}
x
=
c
{\displaystyle x=c}
テトレーション もまた初等的でない原始帰納的関数である。
クラス ELEMENTARY はレベル3のグジェゴルチク階層 、深さ2のループプログラムで計算可能な関数のクラス、時間計算量 が指数関数の定数回の反復で抑えられる関数のクラスなどと一致する。
低初等帰納的関数 限定積を用いずに定義できる初等的関数は低初等帰納的 （英 : lower elementary recursive ）という。すなわち、低初等帰納的関数はゼロ関数, 後者関数, 射影関数, 減算関数から始めて関数合成と限定和を取る操作を有限回繰り返して得られる関数をいう。低初等的関数のクラスを LOWER-ELEMENTARY と書く。スコーレムの初等関数としても知られる[1] [2]
初等的関数が潜在的に指数的な増大度を持つが、他方で低初等的関数は多項式の増大度を持つ。すなわち低初等的関数は多項式関数で支配される。したがって指数関数は初等的だが低初等的でない。
これは初等関数における同様の結果のアナロジーとして、低初等的関数もまた幾つかの単純な関数の合成によって記述できる[2] [3]
n
+
1
{\displaystyle n+1}
n
m
{\displaystyle nm}
n
−
.
m
{\displaystyle n\,{\stackrel {.}{-}}\,m}
n
∧
m
{\displaystyle n\wedge m}
⌊
n
/
m
⌋
{\displaystyle \lfloor n/m\rfloor }
2
n
{\displaystyle 2^{n}}
n
m
{\displaystyle n^{m}}
x
y
(
z
+
1
)
{\displaystyle xy(z+1)}
(
x
+
y
)
y
z
+
x
+
z
x
+
1
{\displaystyle (x+y)^{yz+x}+z^{x+1}}
2
2
x
{\displaystyle 2^{2^{x}}}
n
∧
m
{\displaystyle n\wedge m}
ELEMENTARY の基底 初等的関数のクラスは次の何れかの集合と射影の合成に関する閉包と一致する：
{
n
+
1
,
n
−
.
m
,
⌊
n
/
m
⌋
,
n
m
}
{\displaystyle \{n+1,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,n^{m}\}}
{
n
+
m
,
n
−
.
m
,
⌊
n
/
m
⌋
,
2
n
}
{\displaystyle \{n+m,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,2^{n}\}}
{
n
+
m
,
n
2
,
n
mod
m
,
2
n
}
{\displaystyle \{n+m,n^{2},n{\bmod {m}},2^{n}\}}
n
−
˙
m
=
max
{
n
−
m
,
0
}
{\displaystyle n{\dot {-}}m=\max\{n-m,0\}}
[4]
記述的特徴付け 記述計算量 の観点から見ると ELEMENTARY は 高階論理 で表されるクラスに一致する。[5]
N
T
I
M
E
(
2
2
⋯
2
O
(
n
)
)
=
∃
H
O
i
{\displaystyle \mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists {}HO^{i}}
⋯
{\displaystyle \cdots }
i
{\displaystyle i}
∃
H
O
i
{\displaystyle \exists {}HO^{i}}
i
{\displaystyle i}
i
−
1
{\displaystyle i-1}
関連項目 References
^ 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 . ^ a b 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 .
^ Volkov, Sergey (2016). "Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation]". arXiv :1611.04843 ^ Mazzanti, S., "Plain Bases for Classes of Primitive Recursive Functions", Mathematical Logic Quarterly, 48 (2002) 93-104 ^ Lauri Hella and José María Turull-Torres (2006), “Computing queries with higher-order logics” , Theoretical Computer Science (Essex, UK: Elsevier Science Publishers Ltd.) 355 (2): 197–214, doi :10.1016/j.tcs.2006.01.009 ,
ISSN 0304-3975 , http://portal.acm.org/citation.cfm?id=1142890.1142897
Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3
主な複雑性クラス (一覧)
実用的な時間で解けるクラス
実用的な時間で解けないと疑われているクラス
実用的な時間では解けないクラス
クラス階層
クラスの族
