ในทฤษฎีความซับซ้อนของการคำนวณลำดับชั้นเลขชี้กำลังเป็นลำดับชั้นของคลาสความซับซ้อนที่เป็นอนาล็อกของลำดับชั้นพหุนามในเวลาเลขชี้กำลังเช่นเดียวกับในทฤษฎีความซับซ้อนอื่นๆ คำว่า “เลขชี้กำลัง” ถูกใช้ในสองความหมายที่แตกต่างกัน (ขอบเขตเลขชี้กำลังเชิงเส้นสำหรับค่าคงที่cและขอบเขตเลขชี้กำลังแบบเต็ม) ซึ่งนำไปสู่ลำดับชั้นเลขชี้กำลังสองเวอร์ชัน^{[ 1 ] [ 2 ]}บางครั้งลำดับชั้นเหล่านี้ก็ถูกเรียกว่า ลำดับชั้นเลขชี้กำลัง แบบอ่อนเพื่อแยกความแตกต่างจาก ลำดับชั้นเลขชี้กำลัง แบบแข็งซึ่งประกอบด้วยลำดับชั้นแบบอ่อนทั้งสอง^{[ 2 ] [ 3 ]}${\displaystyle 2^{cn}}$${\displaystyle 2^{n^{c}}}$

คลาสความซับซ้อน EH คือการรวมกันของคลาสต่างๆสำหรับทุกkโดยที่และ(กล่าวคือ ภาษาที่คำนวณได้ในเวลาที่ไม่แน่นอนสำหรับค่าคงที่c บางค่า โดยมีออราเคิล ) นอกจากนี้ยังมีการกำหนด ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$${\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}}$${\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$${\displaystyle 2^{cn}}$${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$

${\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}}}$

ลำดับชั้นเลขชี้กำลังที่แข็งแกร่ง ซึ่งแสดงด้วย SEH คือการรวมกันของ NE, NP ^NE , NP ^{NP NE}และอื่นๆ^{[ 4 ]}

จะได้คลาสเดียวกันหากเราแทนที่ NE ด้วย NEXP ^{[ 4 ]}

E ⊆ NE ⊆ EH⊆ ESPACE ,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE ,

EH ⊆ EXPH.

สวนสัตว์แห่งความซับซ้อน :คลาส EH