# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# 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.

03-10-2013 05:06:04