Talk:Exponential hierarchy

Can I ask for references where this concept is defined? I tried searching for "exponential hierarchy" on google but found a paper with a different definition [1]. Andris 14:13, May 19, 2004 (UTC)

I was relying on Papadimitriou, "Computational Complexity", page 498. The paper you cite is discussing the strong exponential hierarchy (which generalizes E and NE rather than EXPTIME and NEXPTIME). Gdr 11:23, 2004 May 20 (UTC)

Thanks! I found Papadimitriou's book and it's there. I am still wondering if the exponential hierarchy with quantifiers that he briefly defines on page 497 is the same as the one from page 498 that you quote. I will think about that. Andris 22:13, May 20, 2004 (UTC)

Yes, these two mentions of "exponential hierarchy" are in adjacent paragraphs and are referring to the same thing! Gdr 15:38, 2004 Jul 20 (UTC)

This article is extremely misleading. In every single paper I’ve seen, except for the (rather unclear, because it seems to use the term in two completely different meanings) offending quote from Papadimitriou, the unqualified term “exponential hierarchy” refers to one of the following two things:

• $\mathrm {EH} =\bigcup _{n=1}^{\infty }\Sigma _{n}^{E}$, where $\Sigma _{n}^{E}=\mathrm {NE} ^{\Sigma _{n-1}^{P}}$ (mind the P). One also defines $\Pi _{n}^{E}=\mathrm {coNE} ^{\Sigma _{n-1}^{P}}$, $\Delta _{n}^{E}=\mathrm {E} ^{\Sigma _{n-1}^{P}}$. Equivalently, a language L is in $\Sigma _{n}^{E}$ iff it can be written as

$x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{n}\,R(x,y_{1},\dots ,y_{n}),$

where $R(x,y_{1},\dots ,y_{n})$ is computable in time $2^{O(|x|)}$ (which implicitly bounds the length of y_i, so that I don’t have to write it in the formula above). Also equivalently, EH = ATIMEALT(2^O(n),O(1)).

• $\mathrm {EXPH} =\bigcup _{n=1}^{\infty }\Sigma _{n}^{EXP}$, where $\Sigma _{n}^{EXP}=\mathrm {NEXP} ^{\Sigma _{n-1}^{P}}$, and again $\Pi _{n}^{EXP}=\mathrm {coNEXP} ^{\Sigma _{n-1}^{P}}$, $\Delta _{n}^{EXP}=\mathrm {EXP} ^{\Sigma _{n-1}^{P}}$. Equivalently, a language L is in $\Sigma _{n}^{EXP}$ iff it can be written as

$x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{n}\,R(x,y_{1},\dots ,y_{n}),$

where $R(x,y_{1},\dots ,y_{n})$ is computable in time $2^{|x|^{O(1)}}$ (which again implicitly bounds the length of y_i). Equivalently, $\mathrm {EXPH} =\mathrm {ATIMEALT} (2^{n^{O(1)}},O(1))$.

We have $\mathrm {EH} \subseteq \mathrm {EXPH} \subseteq \mathrm {EXPSPACE} \subseteq 2{\text{-}}\mathrm {EXPTIME}$ (in Papadimitrou’s notation; more commonly, 2-EXPTIME is denoted EEXP), so these hierarchies are much smaller than what this article defines. The so-called “strong exponential hierarchy” is yet something different, and I’ve only encountered it in the Hemachandra paper which shows that it collapses (and which, incidentally, also defines plain “exponential hierarchy” to stand for EH as above).—Emil J. 14:26, 9 September 2013 (UTC)

I fixed the article.—Emil J. 17:31, 7 October 2013 (UTC)