Exponential hierarchy

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the exponential hierarchy is a hierarchy of <a href="/facts/Complexity_class/IIKrcTbP">complexity classes</a> that is an <a href="/facts/EXPTIME/GbTmY8t5">exponential time</a> analogue of the <a href="/facts/Polynomial_hierarchy/73N468Dv">polynomial hierarchy</a>. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds 
 
 
 
 
 2
 
 c
 n
 
 
 
 
 {\displaystyle 2^{cn}}
 
 for a constant c, and full exponential bounds 
 
 
 
 
 2
 
 
 n
 
 c
 
 
 
 
 
 
 {\displaystyle 2^{n^{c}}}
 
), leading to two versions of the exponential hierarchy. This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy.

Exponential hierarchy open-in-new

Exponential hierarchy