Talk:Exponential hierarchy

From Wikipedia, the free encyclopedia

You have new messages (last change).

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)
Retrieved from "http://en.wikipedia.org../../../e/x/p/Talk%7EExponential_hierarchy_9aa9.html"