指数階層

計算複雑性理論において、指数階層は、多項式階層の指数時間類似物である計算複雑性クラスの階層である。計算複雑性理論の他の部分と同様に、「指数」は2つの異なる意味（定数cに対する線形指数境界と完全指数境界）で使用され、指数階層にも2つのバージョンが存在する。^{[1] [2]この階層は、}強い指数階層と区別するために、弱い指数階層と呼ばれることもある。^{[2] [3]}${\displaystyle 2^{cn}}$${\displaystyle 2^{n^{c}}}$

計算量クラスEHは、すべてのkに対するクラスの和集合であり、ここで（つまり、オラクルを持つ定数cに対して非決定的時間で計算可能な言語）であり、である。また、次のように定義される。 ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$${\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$${\displaystyle 2^{cn}}$${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$ ${\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}}$

${\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$そして${\displaystyle \Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

同等の定義は、言語Lが属する場合、そしてその場合のみ、それが次の形式で記述できるというもの である。${\displaystyle \Sigma _{k}^{\mathsf {E}}}$

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

ここで、は時間内に計算可能な述語です（これはy _iの長さを暗黙的に制限します）。また、同等に、 EH は、一定数の交替を伴うcに対して、交替チューリングマシンで時間内に計算可能な言語のクラスです。 ${\displaystyle R(x,y_{1},\ldots,y_{n})}$${\displaystyle 2^{c|x|}}$${\displaystyle 2^{cn}}$

EXPH は、クラス の和集合です。ここで、 (オラクルを使用して定数cに対して非決定的時間で計算可能な言語)、であり、また次のようになります。 ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}}$${\displaystyle 2^{n^{c}}}$${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$${\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}}$

${\displaystyle \Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

言語Lは次のように書ける場合のみ 存在する。${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

ここで、 は何らかのcに対して時間内に計算可能であり、これもまた暗黙的にy _iの長さを制限します。同様に、 EXPH は、常に多くの交替を伴う交替チューリングマシン上で時間内に計算可能な言語のクラスです。 ${\displaystyle R(x,y_{1},\ldots,y_{k})}$${\displaystyle 2^{|x|^{c}}}$${\displaystyle 2^{n^{c}}}$

E ⊆ NE ⊆ EH⊆ ESPACE、

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE、

EH ⊆ EXPH.

複雑動物園：クラス EH