グジェゴルチク階層

グジェゴルチク階層（ぐじぇごるちくかいそう、英: Grzegorczyk hierarchy、発音：[ɡʐɛˈɡɔrt͡ʂɨk]）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者アンジェイ・グジェゴルチク（英語版）に因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。

まず自然数 i で添字付けられた関数族 E_i を導入する。まず次のように定義する：

${\displaystyle E_{0}(x,y)=x+y}$

${\displaystyle E_{1}(x)=x^{2}+2}$

${\displaystyle E_{n}(x)=E_{n-1}^{x}(2)}$ （ただし n > 1）

これらの関数からグジェゴルチク階層を定義する。${\displaystyle {\mathcal {E}}^{n}}$ は n番目の階層であり、次の関数からなる：

1. E_k （ただし k < n）
2. ゼロ関数 (Z(x) = 0);
3. 後者関数 (S(x) = x + 1);
4. 射影関数 (${\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}}$);
5. （一般）合成関数 （もし h, g₁, g₂, ... と g_m が${\displaystyle {\mathcal {E}}^{n}}$ に属すならば ${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))}$ も同様）^{[note 1]}; および
6. 限定（原始）再帰 （もし g, h と j が ${\displaystyle {\mathcal {E}}^{n}}$ に属し ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$, ${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$, ${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$ ならば、 f もまた ${\displaystyle {\mathcal {E}}^{n}}$ に属す)^{[note 1]}

換言すれば ${\displaystyle {\mathcal {E}}^{n}}$ は ${\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}}$ を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。

これらの集合は明らかに階層を成す。

${\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }$

実際これらは ${\displaystyle B_{n}}$ の閉包であって ${\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots }$ となっているからである。

これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば

${\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }$

というのも、ハイパー演算子 ${\displaystyle H_{n}}$ は ${\displaystyle {\mathcal {E}}^{n}}$ に属すが ${\displaystyle {\mathcal {E}}^{n-1}}$ には属さないからである。

• ${\displaystyle {\mathcal {E}}^{0}}$ は次を含む： x+1, x+2, ...
• ${\displaystyle {\mathcal {E}}^{1}}$ は全ての加法関数を備える： x+y, 4x, ...
• ${\displaystyle {\mathcal {E}}^{2}}$ は全ての乗法関数を備える： xy, x⁴, ...
• ${\displaystyle {\mathcal {E}}^{3}}$ は全ての指数関数を備える： x^y, 2^22x さらにこの階層は初等帰納的関数のクラスや反復指数時間で計算可能な関数のクラスなどと一致する
• ${\displaystyle {\mathcal {E}}^{4}}$ は全てのテトレーション関数を備える。

${\displaystyle {\mathcal {E}}^{n}}$ の定義は再帰が限定 （ある j ${\displaystyle \in {\mathcal {E}}^{n}}$ に対して ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$）されていることと、${\displaystyle (E_{k})_{k<n}}$ が明示的に導入されることを除けば 原始帰納的関数のクラス PR の定義に似ている。グジェゴルチク階層は原始再帰の強さを制限しているものと見ることができる。

この事実からグジェゴルチク階層に属す全ての関数は原始帰納的関数であること（すなわち ${\displaystyle {\mathcal {E}}^{n}\subseteq PR}$）が示される。したがって

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq PR}$

さらに全ての原始帰納的関数が何れかの階層に属すことも示される（Rose 1984; Gakwaya 1997）。つまり

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}=PR}$

また ${\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots }$ は原始帰納的関数のクラス PR の分割となっている。さらに各々の領域は潰れていない。

グジェゴルチク階層は超限順序数に一般化できる。そのような拡張として急成長階層が定義される。それには、極限順序数に対する生成関数 ${\displaystyle E_{\alpha }}$ を帰納的に定義しなければならない（後続型順序数に対しては ${\displaystyle E_{\alpha +1}(n)=E_{\alpha }^{n}(2)}$ とすればよい。) もし極限順序数 ${\displaystyle \lambda }$ の基本列 ${\displaystyle \lambda _{m}}$ を作る一般的な方法があれば、 生成関数は ${\displaystyle E_{\lambda }(n)=E_{\lambda _{n}}(n)}$ と定義できる。ところがこの定義は基本列を作る方法に依存する。Rose（1984）は任意の順序数 α < ε₀ に対する基本列の一般的な構成法を提案した。

独自の拡張としては Martin Löb と Stan S. Wainer（1970）による Löb–Wainer 階層がある。

• 原始帰納的関数
• 初等帰納的関数
• ループプログラム
• 急成長階層

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
• Cichon, E. A.; Wainer, S. S. (1983), “The slow-growing and the Grzegorczyk hierarchies”, The Journal of Symbolic Logic 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812, MR704094 
• Gakwaya, J.–S. (1997), A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability
• Grzegorczyk, A. (1953), Some classes of recursive functions, Rozprawy matematyczne, Vol 4, pp. 1–45.
• Löb, M.H. and Wainer, S.S., "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Math. Logik Grundlagenforschung 14, 1970 pp. 198–199.
• Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3
• Wagner, K. and Wechsung, G. (1986), Computational Complexity, Mathematics and its Applications v. 21. ISBN 978-90-277-2146-4

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ