In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, starting with EXPTIME:
and continuing with
and so on.
We have P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …. Unlike the analogous case for the polynomial hierarchy, the time hierarchy theorem guarantees that these inclusions are proper; that is, there are languages in EXPTIME but not in P, in 2-EXPTIME but not in EXPTIME and so on.
The union of all the classes in the exponential hierarchy is the class ELEMENTARY.
Famous quotes containing the word hierarchy:
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)