初等的でない問題

計算複雑性理論 において、 非初等問題^{[ 1 ]}は、クラスELEMENTARYのメンバーではない問題です。クラスとしては、NONELEMENTARYと表記されることもあります。つまり、初等再帰関数によって時間制限されるアルゴリズム解を持たないすべての決定問題が含まれます。これらの関数は、指数関数の固定高さの塔（例えば、${\displaystyle O(2^{2^{n}})}$すべての原始的な再帰関数が基本関数であるとは限りません。たとえば、テトレーションは急速に増加するため、基本クラスには含まれません。

基本的な問題を超えた決定可能な問題の階層は、通常、急速に成長する階層に沿って提示されます。^{[ 2 ]}

階層の関数を次のように定義する。${\displaystyle F_{0},F_{1},\dots ,F_{\omega },F_{\omega +1},\dots }$各序数について${\displaystyle \alpha }$クラスを定義します${\displaystyle {\mathcal {F}}_{\alpha }}$時間内に計算可能な関数のクラスである${\displaystyle F_{\alpha }^{(k)}(n)}$、ある正の定数に対して${\displaystyle k}$。ここで、表記法${\displaystyle F^{(k)}}$関数反復を示します。これは、適用によって得られる関数です。${\displaystyle F}$繰り返し、${\displaystyle k}$回数。つまり、$${\displaystyle {\mathcal {F}}_{\alpha }:=\bigcup _{k=1}^{\infty }{\mathsf {FDTIME}}(F_{\alpha }^{(k)}(n))}$$さて、定義します${\displaystyle {\mathsf {F}}_{\alpha }}$複雑性クラスになる${\displaystyle \bigcup _{\beta <\alpha ,p\in {\mathcal {F}}_{\beta }}{\mathsf {DTIME}}(F_{\alpha }(p(n)))}$。

定義によれば、

• 初歩的：時間内に決定可能な問題のクラス${\displaystyle f(n)}$、 どこ${\displaystyle f(n)}$は固定高さの指数タワー関数です。言い換えれば、${\displaystyle {\mathsf {ELEMENTARY}}={\mathsf {DTIME}}(n)\cup {\mathsf {DTIME}}(2^{n})\cup {\mathsf {DTIME}}(2^{2^{n}})\cup \cdots }$。
• タワー：${\displaystyle f(n)={\;}^{p(n)}2}$、 どこ${\displaystyle p(n)}$は固定高さの指数タワー関数であり、上付き文字はテトラレーションを表します。言い換えれば、${\displaystyle f(n)=F_{3}(p(n))}$。 言い換えると、${\displaystyle {\mathsf {TOWER}}={\mathsf {DTIME}}({}^{n}2)\cup {\mathsf {DTIME}}({}^{2^{n}}2)\cup {\mathsf {DTIME}}({}^{2^{2^{n}}}2)\cup \cdots }$。 言い換えると、${\displaystyle {\mathsf {TOWER}}:={\mathsf {F}}_{3}}$。
• 広報：${\displaystyle f(n)}$は原始的な再帰関数です。言い換えれば、${\displaystyle {\mathsf {PR}}={\mathsf {DTIME}}(F_{1})\cup {\mathsf {DTIME}}(F_{2})\cup {\mathsf {DTIME}}(F_{3})\cup \cdots }$。
• ACK:${\displaystyle f(n)=A(n,n)=F_{\omega }(n)}$、 どこ${\displaystyle A}$はアッカーマン関数です。言い換えれば、${\displaystyle {\mathsf {ACK}}:={\mathsf {F}}_{\omega }}$

時間階層定理によれば、ELEMENTARYとPRには完全な問題は存在しない。しかし、TOWERとACKには完全な問題がある。

タワー- 完全な問題:

• スターフリー式等価性（SFEq）^{[ 2 ]}
• 1つの後継者の弱い単項二階論理（WS1S）の充足可能性^{[ 2 ]}
• WVO Quineの1階述語論理の溝付き断片の充足可能性^{[ 3 ]}
• 単純型ラムダ計算における2つの閉じた項のβ変換可能性^{[ 4 ] [ 5 ]}

ACK - 問題完了:

• ベクトル加算システム（VAS）における到達可能性。^{[ 6 ] [ 7 ]}
• ラベル付きベクトル加算システム（VASS）における到達可能性^{[ 8 ]}
• ペトリネットにおける到達可能性。^{[ 9 ] [ 7 ]}

その他の非初等的だが決定可能な問題：

• 正規表現の相補性の問題^{[ 10 ]}
• 2 つの後継者を持つ単項二次理論（ S2S を参照）^{[ 11 ]}
• 少なくとも１つの二項関数記号を含むシグネチャ内の任意の項代数の一次理論^{[ 12 ]}
• 有限包含問題 (FCP): 有限到達可能集合を持つ 2 つの VAS が与えられた場合${\displaystyle \operatorname {Reach} (V_{1}),\operatorname {Reach} (V_{2})}$決定する${\displaystyle \operatorname {Reach} (V_{1})\subset \operatorname {Reach} (V_{2})}$その正確な複雑さのレベルは不明です。到達可能集合が有限であるかどうかを判定することはEXPSPACE完全であることに注意してください。^{[ 2 ]}
• 特定のクラスの構造化遷移システムのカバー可能性と終了性の問題が知られている。${\displaystyle {\mathsf {F}}_{\omega },{\mathsf {F}}_{\omega ^{\omega }},{\mathsf {F}}_{\omega ^{\omega ^{\omega }}},}$または${\displaystyle {\mathsf {F}}_{\epsilon _{0}}}$-完了。^{[ 13 ]}

多数のリストがまとめられています。^{[ 2 ]}