ELEMENTARY

ELEMENTARY クラスの概要

計算複雑性理論において、ELEMENTARYは特に重要な複雑性クラスです。このクラスは、指数関数階層の和集合として定義されます。

定義と構成

ELEMENTARYクラスは次のように表されます。

• -

$${\displaystyle ELEMENTARY = EXP \cup 2EXP \cup 3EXP \cup \cdots}$$

• - $${\displaystyle = [DTIME] \cup [DTIME] \cup [DTIME] \cup \cdots}$$

このように、ELEMENTARYに属する関数は、初等帰納的、あるいは単に初等的と呼ばれます。これは、カルマールによって名付けられた名称です。

初等帰納的関数の特徴

初等的関数は、自然数に作用するものであり、その基本的な性質を理解するために以下の基本関数が挙げられます:

• - ゼロ関数: Z(x) = 0
• - 後者関数: S(x) = x + 1
• - 射影関数: P(μ, ν)(x) = x_μ
• - 減算関数: x -˙ y = max(x - y, 0)

これらの基本関数を組み合わせることで、初等的関数が形成されます。例えば、合成、限定和、限定積といった操作がこのプロセスに含まれます。

具体的な例

具体的な初等的関数には、次のものがあります:

• - 乗算関数: x ⋅ y = $${\displaystyle \sum_{z < y} x}$$
• - 加算関数: x + y = $${\displaystyle S(x) \cdot S(y) \dot{-} S(x \cdot y)}$$
• - 冪乗関数: x^y = $${\displaystyle \prod_{z < y} x}$$
• - 素数列: p_n = 2, 3, 5, 7, 11, …

このように、ELEMENTARYクラス内の関数は多様であり、様々な形で定義されます。

ELEMENTARYとNONELEMENTARY

ELEMENTARYに属さない関数はNONELEMENTARYとして知られています。特に、原始帰納的問題の中にはELEMENTARYに当てはまらないものも存在します。たとえば、LOWER-ELEMENTARYはEXPTIMEに含まれ、ELEMENTARYよりも下位に位置します。

ELEMENTARYの階層

ELEMENTARYの性質を考察すると、クラスは以下の階層に一致します:

• - LEVEL 3のグジェゴルチク階層
• - 深さ2のループプログラムで計算可能な関数
• - 時間計算量が指数関数の定数けた数の反復で抑えられる関数

低初等帰納的関数とその特徴

さらに限定積を使用せずに定義できる関数をLOWER-ELEMENTARYと呼びます。これらは、次の方向で定義されます:

• - ゼロ関数、後者関数、射影関数、減算関数から始まり、関数合成と限定和を繰り返して得られる関数です。

LOWER-ELEMENTARY関数は、多項式の増大度を持ち、従って多項式関数に抑えられます。具体的には、指数関数は初等的ですが、LOWER-ELEMENTARYには含まれません。

結論

ELEMENTARYクラスは計算論理における基盤を形成し、様々な数学的および計算的問題に対する理解を深めるための鍵となります。このクラスに属する初等的関数は、計算の基礎的構造を把握するために重要であり、多様な応用分野にも関連しています。

関連項目として、初等関数算術や原始帰納的関数の扱いが挙げられます。

もう一度検索