Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Exponential hierarchy

In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, starting with EXP:

$\rm{EXP} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(2^{n^k})$

and continuing with

$\rm{2EXP} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(2^{2^{n^k}})$

$\rm{3EXP} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(2^{2^{2^{n^k}}})$

and so on.

We have P ⊂ EXP ⊂ 2EXP ⊂ 3EXP &sub …. Unlike the analogous case for the polynomial hierarchy, the time hierarchy theorem guarantees that these inclusions are proper: that is, there are languages in EXP but not in P, in 2EXP but not in EXP and so on.

The union of all the classes in the exponential hierararchy is the class ELEMENTARY.

Categories: Complexity classes

Science Fair Project Encyclopedia Contents Page

03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

Science Fair Project Encyclopedia

Exponential hierarchy