<p>The Fourier Hierarchy as defined in "<a href="http://www.sciencedirect.com/science/article/pii/S0304397505001878" rel="nofollow noreferrer">Yaoyun Shi, Quantum and classical tradeoffs</a>."</p>

<p>From the <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:F#fh" rel="nofollow noreferrer">complexity zoo</a>:</p>

<blockquote>
  <p><span class="math-container">$\mathsf{FH}_k$</span> is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with <span class="math-container">$k$</span> levels of Hadamard gates and all other gates preserving the computational basis.</p>
  
  <ul>
  <li><span class="math-container">$\mathsf{FH}_0 = \mathsf{P}$</span></li>
  <li><span class="math-container">$\mathsf{FH}_1 = \mathsf{BPP}$</span></li>
  <li><span class="math-container">$\mathsf{FH}_2$</span> contains factoring because of <a href="https://people.eecs.berkeley.edu/~vazirani/s09quantum/notes/lecture6.pdf" rel="nofollow noreferrer">Kitaev's phase estimation algorithm</a>.</li>
  </ul>
  
  <p>It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, <span class="math-container">$\mathsf{FH}_k$</span> is strictly contained in <span class="math-container">$\mathsf{FH}_{k+1}$</span>). </p>
</blockquote>

CC BY-SA 4.0
2011-07-11T03:17:36.450Z
2019-09-23T08:02:00.437Z
2019-09-23T08:02:00.437Z
Robin Kothari
<p>-- Along the lines of "anti-hierarchies", <a href="http://en.wikipedia.org/wiki/Gap_theorem">Borodin's gap theorem</a> might be worth mentioning.</p>

<blockquote>
  <p><strong>Theorem.</strong> For every total computable function $f : {\mathbb N} \rightarrow {\mathbb N}$ such that $f(n) = \Omega(n)$, there is a total computable $g : {\mathbb N} \rightarrow {\mathbb N}$ such that ${\sf TIME}[g(n)] = {\sf TIME}[f(g(n))]$. </p>
</blockquote>

<p>This would contradict the time hierarchy theorem except that $g$ is not time constructable (indeed this is why we must have constructability assumptions in the statements of most complexity hierarchies).</p>

<p>-- There are also interesting strengthenings of the usual time hierarchies, such as:</p>

<p>$${\sf TIME}[n^k] \not\subseteq i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$$</p>

<p>(there are problems in time $n^k$ cannot be successfully solved by any time $n^{k-1}$ time machine using $n-\log n$ bits of advice, even for on just infinitely many input lengths). The proof is easy: let $\{M_i\}$ list the $n^{k-1}$ time machines that take $n-\log n$ bits of advice as a second input. Define $M&#39;(x)$ which splits $x$ into $x=yz$ where $|z|=\log |x|$, runs $M_z(x,y)$, and outputs the opposite answer. Then $L(M&#39;) \notin i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$.</p>

<p>-- The lack of known time hierarchies in certain situations should be considered (as open problems). For example, is ${\sf BPTIME}[n] = {\sf BPP}$?</p>

CC BY-SA 3.0
2011-07-14T03:31:24.110Z
Is it $\mathsf{TIME}[g(n)] = \mathsf{TIME}[f(g(n))]$? otherwise the statement is not interesting: just choose $g(n) = n$.
Sasho Nikolov
CC BY-SA 3.0
2011-07-23T16:05:20.610Z
@Sasho, it appears so. The statement of Borodin's gap theorem (via the link) says as much.
Daniel Apon
CC BY-SA 3.0
2011-07-10T22:03:09.290Z
2011-08-06T16:08:18.953Z
2011-08-06T16:08:18.953Z
Ryan Williams
<p>Sipser showed a depth hierarchy within $AC^0$, that is, that depth $d+1$ circuits of poly size are more powerful than depth $d$ circuits of poly size:</p>

<p>Sipser, M. <a href="http://dx.doi.org/10.1145/800061.808733">Borel sets and circuit complexity</a>. STOC 1983.</p>

CC BY-SA 3.0
2011-07-10T17:18:56.633Z
2011-07-10T17:18:56.633Z
Joshua Grochow
<p>The Complexity Zoo gives you some <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:List_of_Hierarchies" rel="nofollow noreferrer">hierarchies</a>. Amongst them, the Counting Hierarchy and the Boolean Hierarchy were not already cited.</p>

<p><strong>[EDIT]</strong> To make my answer more informative, a quick definition of the Counting Hierarchy.</p>

<ul>
<li><span class="math-container">${\sf C_0P} = {\sf P}$</span></li>
<li><span class="math-container">${\sf C_1P} = {\sf PP}$</span></li>
<li><span class="math-container">${\sf C_{k+1}P} = {\sf PP^{C_kP}}$</span></li>
</ul>

<p>Then, as for the polynomial hierarchy, <span class="math-container">$\sf CH$</span> is defined as <span class="math-container">$\bigcup_k {\sf C_kP}$</span>. </p>

<p>The counting hierarchy was defined by Wagner [Wag86]. Links to the theory of threshold circuits were discovered by Allender &amp; Wagner [AW93]. Much more recently, Bürgisser [Bür09] also used the counting hierarchy to relate Valiant's model to the <span class="math-container">$\tau$</span>-conjecture of Shub and Smale. In particular, he proved that the <span class="math-container">$\tau$</span>-conjecture implies a superpolynomial lower bound for the permanent.</p>

<p><strong>[Wag86]</strong> K.W. Wagner. <a href="https://link.springer.com/article/10.1007/BF00289117" rel="nofollow noreferrer">The complexity of combinatorial problems with succinct input representation</a>. <em>Acta Mathematica</em> 23(3), 325-356, 1986.<br>
<strong>[AW93]</strong> E. Allender &amp; K.W. Wagner. <a href="https://www.worldscientific.com/doi/abs/10.1142/9789812794499_0035" rel="nofollow noreferrer">Counting hierarchies: polynomial time and constant-depth circuits</a>. <em>Current Trends in Computer Science</em>, 469-483, 1993.<br>
<strong>[Bür09]</strong> P. Bürgisser. <a href="https://www3.math.tu-berlin.de/algebra/work/6dich.pdf" rel="nofollow noreferrer">On defining integers and proving arithmetic circuit lower bound</a>. <em>Computational Complexity</em> 18(1), 81-103, 2009.</p>

CC BY-SA 4.0
2011-07-10T21:40:00.890Z
2019-09-23T08:02:30.230Z
2019-09-23T08:02:30.230Z
Bruno
<p>Goldreich et. al. have hierarchy theorems for property testing:</p>

<ul>
<li>Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
<a href="http://www.wisdom.weizmann.ac.il/~oded/PDF/testHT2.pdf" rel="nofollow noreferrer">Hierarchy Theorems for Property Testing.
Property Testing</a>, Lecture Notes in Computer Science, Vol. 6390, pp. 289-294, Springer, 2010.</li>
</ul>

<p>Also on the <a href="http://eccc.hpi-web.de/report/2008/097/" rel="nofollow noreferrer">ECCC</a>.</p>

CC BY-SA 3.0
2011-07-13T11:00:59.510Z
[here](http://arxiv.org/abs/quant-ph/0201117) it is shown that most properties require $\Omega(n)$ queries in the quantum model. This can be plugged into the proof of the answer's hierarchy theorem to show that it holds for quantum property testing, too. (In fact for any natural computational model with at least one property that requires $\Omega(g(n))$ queries to test, and any computable $f(n) \in O(g(n))$ you have properties which is testable in $\Theta(f(n))$ queries).
Artem Kaznatcheev
CC BY-SA 4.0
2011-07-10T13:23:18.890Z
2019-09-23T08:02:39.090Z
2019-09-23T08:02:39.090Z
Yonatan
<p><a href="http://pages.cs.wisc.edu/~dieter/">Dieter van Melkebeek</a> and coauthors have time and space hierarchies for semantic models with advice, including randomization.</p>

<ul>
<li>Dieter van Melkebeek, Konstantin Pervyshev: <a href="http://pages.cs.wisc.edu/~dieter/Papers/t-hierarchy-ccc06.ps">A Generic Time Hierarchy with One Bit of Advice</a>. Computational Complexity 16(2): 139-179 (2007)</li>
<li>Jeff Kinne, Dieter van Melkebeek: <a href="http://pages.cs.wisc.edu/~dieter/Papers/s-hierarchy-full.pdf">Space Hierarchy Results for Randomized and other Semantic Models</a>. Computational Complexity 19(3): 423-475 (2010)</li>
</ul>

CC BY-SA 3.0
2011-07-10T12:49:33.537Z
2011-07-10T12:49:33.537Z
Tyson Williams
<p>Here are more hierarchies for semantic classes with advice. Specifically, for ZPTIME and RTIME.</p>

<p>Lance Fortnow, Rahul Santhanam, Luca Trevisan. <a href="http://portal.acm.org/citation.cfm?id=1060590.1060642">Hierarchies for Semantic Clases</a>. In STOC'05.</p>

CC BY-SA 3.0
2011-07-11T02:36:55.173Z
2011-07-11T02:36:55.173Z
Marcos Villagra
<p>There is the Zheng-Weihrauch hierarchy for real numbers</p>

<p>X. Zheng and K. Weihrauch.    <a href="https://link.springer.com/chapter/10.1007/3-540-48340-3_3" rel="nofollow noreferrer">The arithmetical hierarchy of real numbers</a>. Mathematical Logic Quarterly.Vol. 47(2001), no.1 51 - 65.</p>

CC BY-SA 4.0
2011-07-10T20:36:25.713Z
2019-09-23T08:02:06.027Z
2019-09-23T08:02:06.027Z
Someone
<p>There is a class $\mathsf{D}$, defined in a 1975 paper by L. Adelman and K. Manders, which is a diophantine analogue of the class $\mathsf{NP}$.
A language $L$ is contained in $\mathsf{D}$ iff there exists a polynomial $P$ such that
$$x \in L \Leftrightarrow \exists y_1, \dots y_n &lt; poly(|x|) \colon ~P(x, y_1,\dots, y_n) = 0.$$
Whether $\mathsf{D}$ equals $\mathsf{NP}$ is an open problem. This equality would show connections between number theory and computer science.</p>

<p>There is a diophantine analogue of the polynomial hierarchy, called the "diophantine hierarchy". The polynomial and diophantine hierarchies are intertwined:
$$\forall i \ge 1,~\Sigma^i D \subset \Sigma^i P \subset \Sigma^{i + 1}D$$</p>

CC BY-SA 3.0
2012-11-06T14:01:23.960Z
Do you mean http://doi.ieeecomputersociety.org/10.1109/SFCS.1975.9 or http://doi.ieeecomputersociety.org/10.1109/SFCS.1976.13 ?
András Salamon
CC BY-SA 3.0
2014-09-03T20:10:42.910Z
$D$ is defined in the second one ("Diophantine Complexity").
GMB
CC BY-SA 3.0
2012-05-28T09:44:54.060Z
2012-11-05T21:18:22.640Z
2012-11-05T21:18:22.640Z
Alexander Knop
<p>In <a href="https://en.wikipedia.org/wiki/Parameterized_complexity" rel="nofollow noreferrer">parameterized complexity</a> theory there are several hierarchies although only the already mentioned <span class="math-container">$\mathsf{W}$</span>-hierarchy appears often in publications. Others are:</p>

<ul>
<li><span class="math-container">$\mathsf{A}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{AW}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{EW}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{LOG}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{M}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{S}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{W^∗}$</span>-hierarchy</li>
<li><span class="math-container">$\mathsf{W^{func}}$</span>-hierarchy</li>
</ul>

<p>They are all described in <a href="https://www.springer.com/gp/book/9783540299523" rel="nofollow noreferrer">Parameterized complexity theory, Flum and Grohe, Birkhäuser, 2006</a>.</p>

CC BY-SA 4.0
2011-07-25T18:10:37.540Z
2019-09-23T19:18:55.260Z
2019-09-23T19:18:55.260Z
Martin Lackner
<p>Not sure if this fits your criteria, but there is the <a href="http://www.sciencedirect.com/science/article/pii/0022000078900491">dot-depth hierarchy</a> of star-free regular languages.</p>

CC BY-SA 3.0
2011-07-11T06:05:23.493Z
2011-07-11T06:05:23.493Z
mhum
<p>Another strict hierarchy: branching programs which only test each bit a limited number of times.  The more tests are allowed, the larger the class of branching programs.
Usually the branching programs are also restricted to polynomial size.
BP<sub>d</sub>(P) is the class of polynomial size branching programs that may test each bit up to $d$ times.</p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#l.2Fpoly" rel="nofollow">L/poly</a> is the union of <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bpdp" rel="nofollow">BP<sub>d</sub>(P)</a> over all <em>d</em>, while BP<sub>d-1</sub>(P) $\subsetneq$ BP<sub>d</sub>(P) for every <em>d</em>.</p>

CC BY-SA 3.0
2011-07-12T09:41:54.320Z
2016-02-20T10:15:02.073Z
2016-02-20T10:15:02.073Z
András Salamon
<p>Here is a <a href="http://arxiv.org/abs/1303.1717" rel="noreferrer">new hierarchy for context-free languages</a> by Tomoyuki Yamakami.</p>

<p>He introduces an oracle mechanism in nondeterministic pushdown automata and notions of Turing and many-one reducibilities. Then a new hierarchy is constructed for Context-free languages (CFL) similar to the polynomial hierarchy. For example, $CFL$, $CFL^{CFL}$, etc. The interesting part of all this is that a collapse in the CFL hierarchy occurs if and only if the polynomial hierarchy collapses. </p>

CC BY-SA 3.0
2014-02-05T00:51:59.573Z
2014-02-05T00:51:59.573Z
Marcos Villagra
<p>The theory of regular languages of infinite trees gave rise to several hierarchies, that are currently studied, with many questions that are still open.</p>
<p>When using automata on infinite trees, the parity condition (or Mostowski condition) is of special interest, because non-deterministic parity automata can express all regular languages of infinite trees, and the structure of the acceptance condition is simpler than others like Rabin or Müller.</p>
<p>Every parity automaton has a <em>rank</em> <span class="math-container">$[i,j]$</span> where <span class="math-container">$i\in\{0,1\}$</span> and <span class="math-container">$i\leq j$</span>, describing the structure of the acceptance condition. Therefore, if a language <span class="math-container">$L$</span> is recognizable by a (det/ND/alt) automaton of rank <span class="math-container">$[i,j]$</span> we say that <span class="math-container">$L$</span> belongs to the <span class="math-container">$[i,j]$</span>-level of the (respectively):</p>
<ul>
<li>deterministic Mostowski hierarchy (not all regular languages)</li>
<li>nondeterministic Mostowski hierarchy</li>
<li>alternating Mostowski hierarchy</li>
</ul>
<p>The level <span class="math-container">$\Sigma_2\cap \Pi_2$</span> of the alternating hierarchy (i.e <span class="math-container">$L$</span> is both Büchi and co-Büchi definable) corresponds to the <em>weak level</em> and is characterised by weak alternating automata, that give themselves rise to a hierarchy:</p>
<ul>
<li>weak index hierarchy (not all regular languages)</li>
</ul>
<p>For all these hierarchies (except the deterministic one), the decidability of membership in a level for a given regular language <span class="math-container">$L$</span> is an open problem. The links between these hierarchies and topological classifications (also called Wadge hierarchy and Borel hierarchy) also pose several open problems. For instance it is conjectured that the weak index hierarchy and the Borel hierarchy coincide. All these hierarchies are known to be strict, and some special cases of deciding the level (especially the low levels, or with input deterministic automaton) have been recently solved.</p>

CC BY-SA 4.0
2014-02-02T14:32:12.003Z
2022-07-27T10:22:09.103Z
2022-07-27T10:22:09.103Z
Denis
<p>The hierarchy for circuit size, see
<a href="https://cstheory.stackexchange.com/questions/5110/time-hierarchy-theorem-for-circuit-complexity">previous question</a>.</p>

CC BY-SA 3.0
2011-07-11T14:58:39.710Z
2011-07-11T14:58:39.710Z
2017-04-13T12:32:28.117Z
Manu
<p>There are hierarchies in propositional proof complexity similar to those in circuit complexity. E.g. $G_i$ propositional roof systems are similar to $\mathsf{PH}$, C-Frege proof systems for $C \subset \mathsf{P}$ are similar to circuit complexity classes $C$, and so on.</p>

<p>There are also hierarchies in bounded arithmetics, e.g. $\mathsf{S^i_j}$ theories, etc.</p>

CC BY-SA 3.0
2011-08-06T13:29:39.653Z
2011-08-06T13:29:39.653Z
Kaveh
<p>Elaborating on one of the bullet points mentioned by the OP (GoldreichKNR09): there are several hierarchy theorems in property testing and proofs of proximity, relating to the query complexity, the adaptivity, or the testability with regard to number of rounds (for proofs of proximity). See, e.g.,</p>

<ul>
<li><em>Hierarchy Theorems for Property Testing</em>, Oded Goldreich, Michael KrivelevichIlan Newman, and Eyal Rozenberg, 2012.
<a href="https://link.springer.com/article/10.1007/s00037-011-0022-4" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00037-011-0022-4</a> <strong>[mentioned by the OP]</strong></li>
<li><em>A Hierarchy Theorem for Interactive Proofs of Proximity</em>, Tom Gur and Ron Rothblum, 2017.
<a href="http://drops.dagstuhl.de/opus/volltexte/2017/8153/" rel="nofollow noreferrer">http://drops.dagstuhl.de/opus/volltexte/2017/8153/</a></li>
<li><em>Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity</em>, Oded Goldreich, 2018.
<a href="https://eccc.weizmann.ac.il/report/2018/098/" rel="nofollow noreferrer">https://eccc.weizmann.ac.il/report/2018/098/</a></li>
<li><em>An adaptivity hierarchy theorem for property testing</em>, Clément Canonne and Tom Gur, 2018.
<a href="https://link.springer.com/article/10.1007%2Fs00037-018-0168-4" rel="nofollow noreferrer">https://link.springer.com/article/10.1007%2Fs00037-018-0168-4</a></li>
</ul>

CC BY-SA 4.0
2019-07-01T22:09:19.983Z
Pointer to [this answer](https://cstheory.stackexchange.com/a/7305/13319), which focuses on the first one (GoldreichKNR09).
Clement C.
CC BY-SA 4.0
2019-07-01T21:53:16.200Z
2019-07-01T21:53:16.200Z
Clement C.
<p>From <a href="https://cs.stackexchange.com/questions/114676/planar-regular-languages">this question on cs.stackexchange</a>, I became aware of the <strong>genus hierarchy of regular languages</strong>. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper.  </p>

<ol>
<li>Bonfante, Guillaume, and Florian Deloup. "<a href="https://arxiv.org/pdf/1301.4981.pdf" rel="nofollow noreferrer">The genus of regular languages.</a>" Mathematical Structures in Computer Science 28.1 (2018): 14-44.</li>
</ol>

CC BY-SA 4.0
2019-09-13T14:38:56.480Z
2019-09-13T14:38:56.480Z
mhum
<p>Lasserre Hierarchy: <em>An</em> Hierarchy of progressively stronger (i.e., tighter, in the sense of integrality gaps) SDP relaxations of fractional polytopes</p>
<ul>
<li>J. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1
programs. In IPCO, pages 293–303, 2001.</li>
<li>J. Lasserre. Global optimization with polynomials and the problem of
moments. SIAM Journal on Optimization, 11(3):796–817, 2001.</li>
</ul>
<p>There are other hierarchies of that kind (Sherali-Adams, Lovasz-Schrijver etc.) but they are all subsumed by Lasserre.</p>

CC BY-SA 4.0
2022-07-28T08:31:02.653Z
2022-07-28T08:31:02.653Z
PsySp
<p>Counting Polynomial Hierarchy, #PH for short. First level is #P then #NP... etc. </p>

CC BY-SA 3.0
2012-05-29T02:28:23.377Z
2012-05-29T02:28:23.377Z
Tayfun Pay
<p>The Polynomial Hierarchy in communication complexity as defined by Babai, Frankl, and Simon (see <a href="http://dl.acm.org/citation.cfm?id=1382962" rel="nofollow">the original paper here</a> and without the paywall <a href="http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/papers/BabaiFS1986.pdf" rel="nofollow">here</a>). The significance of this hierarchy is hard to overestimate. First of all, the disjointness function was introduced by BFS in the same paper that introduced the hierarchy, and the disjointness appeared quite naturally as a coNP$^{cc}$-complete problem. As you know, the disjointness is <strong>THE</strong> function in communication complexity. Secondly, proving lower bounds against the polynomial hierarchy in communication complexity is a major open problem with important implications in other areas of TCS (for example, see <a href="http://eccc.hpi-web.de/report/2015/049/" rel="nofollow">this paper</a> and references therein).</p>

CC BY-SA 3.0
2016-02-23T02:48:53.800Z
Thanks for the addition, I edited your comment to make clear coNP refers to communication complexity (I know this is commonly dropped in the communication complexity community to avoid notation clutter).
chazisop
CC BY-SA 3.0
2016-02-23T01:15:19.680Z
2016-02-23T02:44:27.357Z
2016-02-23T02:44:27.357Z
Denis Pankratov
<p>Consider the Unambiguous Polynomial Hierarchy, <a href="https://arxiv.org/pdf/cs/9907033.pdf" rel="nofollow noreferrer">reference here</a>, original reference here for <a href="https://ieeexplore.ieee.org/document/315812?arnumber=315812" rel="nofollow noreferrer"> the unambiguous polynomial hierarchy</a>(paywalled). While studying the Boolean hierarchy <strong>BH</strong>, and classes such as <strong><span class="math-container">$D_{p}$</span></strong> which have nice results related to closure, and set differences we can explore connections to unambiguous computation.  </p>

<p>As authors(in original reference) state, the classes <span class="math-container">$NC^{k}$</span>, and <span class="math-container">$AC^{k}$</span> give results related to <span class="math-container">$P$</span>, and <span class="math-container">$PSPACE$</span>. With an unambiguous circuit, they could characterize <span class="math-container">$P$</span> differently. Also, related to the above hierarchy is the Promise Unambiguous Hierarchy. Lowness results for the Unambiguous Polynomial Hierarchy- "if there is a sparse Turing Completer set for <span class="math-container">$UP$</span>, hierarchy collapses to lower levels, or into the Promise Unambiguous Case".  </p>

<p>Related for further study of Boolean connectives, and Graph Isomorphism are <a href="https://linkinghub.elsevier.com/retrieve/pii/0022000083900272" rel="nofollow noreferrer"> the Low, and High Hierarchies</a>, also <a href="https://en.wikipedia.org/wiki/Low_and_high_hierarchies" rel="nofollow noreferrer">wikipedia reference</a>.</p>

CC BY-SA 4.0
2019-07-01T18:36:48.700Z
2019-07-08T02:58:26.470Z
2019-07-08T02:58:26.470Z
user3483902
<p>More on the obscure side: My second order heirarchy theorem for fixed point logics in finite model theory. See <a href="http://www.maxky.de/papers/unafp.pdf" rel="nofollow noreferrer">Yet Another Hierarchy Theorem</a>.</p>

CC BY-SA 4.0
2019-09-25T11:00:34.377Z
2019-09-25T11:00:34.377Z
Max Kubierschky
<p>I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, from theology and sociology to biology and chemistry. Seeing that the amount of information is vast, I hope that I could ask for some help by this community. Of course, I don't want you to do a bibliographic search for me, but rather I am asking for two kinds of information:</p>
<ol>
<li><p>Hierarchies and hierarchy theorems that are the result of your work or the work of your colleagues or other people you are familiar with and you think that are not that well known. This could be for example a hierarchy theorem for an obscure computation model that you're interested in or a hierarchy of specific classes, e.g. related with game theory.</p>
</li>
<li><p>Hierarchies and hierarchy theorems that you deem absolutely necessary to be included in a survey of this kind. This would probably be known to me already, but it would be useful to see what hierarchies you consider more important and why. This could be that of the kind &quot;I deem <span class="math-container">$PH$</span> very important because without it we wouldn't be able to do this kind of research&quot; or &quot;Although not so well known, in logic-based TCS we constantly use this hierarchy and I deem it an important tool.&quot; . And yes I do believe that people from logic have a lot of hierarchies to mention, however keep in mind we are talking about hierarchies of problems.</p>
</li>
</ol>
<p>I will keep an updated list here:</p>
<ul>
<li><p><span class="math-container">$DTIME$</span> Hierarchy</p>
</li>
<li><p><span class="math-container">$NTIME$</span> Hierarchy</p>
</li>
<li><p><span class="math-container">$SPACE$</span> Hierarchy</p>
</li>
<li><p>Arithmetical (also known as Kleene) Hierarchy</p>
</li>
<li><p>Hyperarithmetical Hierarchy</p>
</li>
<li><p>Analytical Hierarchy</p>
</li>
<li><p>Chomsky
Hierarchy</p>
</li>
<li><p>Grzegorczyk hierarchy
and the related: Wainer hierarchy
(fast-growing) , Hardy hierarchy<br />
(slow-growing) and the Veblen
hierarchy</p>
</li>
<li><p>Ritchie's hierarchy</p>
</li>
<li><p>Axt's hierarchy (as defined in <a href="https://onlinelibrary.wiley.com/doi/10.1002/malq.19630090106/abstract" rel="nofollow noreferrer">Axt63</a>)</p>
</li>
<li><p>The Loop Hierarchy (defined in <a href="https://www.google.com/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CBgQFjAA&amp;url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9311&amp;rep=rep1&amp;type=pdf&amp;rct=j&amp;q=%22the%20complexity%20of%20loop%20programs%22&amp;ei=U5IpTqznI46q-ga068C-Bg&amp;usg=AFQjCNEX1Eg1Cl4IRfhAeiOtyvxRuttJdQ&amp;sig2=PPOj0_BQFyEJt9tZ890bAw&amp;cad=rja" rel="nofollow noreferrer">MR67</a>)</p>
</li>
<li><p><span class="math-container">$NC$</span> (<span class="math-container">$AC$</span>,<span class="math-container">$ACC$</span>) Hierarchy</p>
</li>
<li><p>The depth hierarchy, as defined in <a href="https://dx.doi.org/10.1145/800061.808733" rel="nofollow noreferrer">Sipser83</a></p>
</li>
<li><p>Polynomial Hierarchy (<span class="math-container">$PH$</span>) and the less refined Meyer-Stockmeyer hierarchy (no dinstinction between quantifiers)</p>
</li>
<li><p>Exponential Hierarchy (<span class="math-container">$ELEMENTARY$</span>)</p>
</li>
<li><p><span class="math-container">$NP$</span>-Intermediate hierarchy
(Ladner's theorem)</p>
</li>
<li><p>The not-so-sturdy <span class="math-container">$AM$</span> (Arthur-Merlin)</p>
</li>
<li><p>The <span class="math-container">$W$</span> (Nondeterministic Fixed-Parameter) hierarchy and the related Alternating W hierarchy (<span class="math-container">$AW$</span>-hierarchy) and <span class="math-container">$W^{*}$</span>-hierarchy (W with Parameter-Dependent Depth)</p>
</li>
<li><p>Counting Hierarchy</p>
</li>
<li><p>Fourier Hierarchy</p>
</li>
<li><p>Boolean Hierarchy (over <span class="math-container">$NP$</span>) , also equal to the Query Hierarchy (over <span class="math-container">$NP$</span>)</p>
</li>
<li><p>Hierarchies for property testing, as seen in <a href="https://doi.org/10.1007/978-3-642-03685-9_38" rel="nofollow noreferrer">GoldreichKNR09</a></p>
</li>
<li><p>The dot-depth hierarchy of star-free regular languages</p>
</li>
<li><p><span class="math-container">$BP_{d}(P)$</span> : The classes solvable by polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times, form a hierarchy for different values of <span class="math-container">$d$</span></p>
</li>
<li><p>The time hierarchy for Circuit Complexity</p>
</li>
<li><p>The polynomial hierarchy in communication complexity</p>
</li>
</ul>
<p>Note: If you do not want to be mentioned exclusively, please say so. As a rule of thumb, I will mention both the community and also the specific person that brings new information to light.</p>

CC BY-SA 3.0
2011-07-10T12:42:40.900Z
This looks very much like a Community Wiki question. Shall I convert it?
Dave Clarke
CC BY-SA 3.0
2011-07-10T12:54:07.633Z
Ladner's theorem can be generalized to get infinite hierarchies between other classes (assuming they are different) such as between **P** and **P^#P**.
Tyson Williams
CC BY-SA 3.0
2011-07-10T13:14:08.040Z
@Dave Clarke please do, I guess I missed hitting that checkbox!
chazisop
CC BY-SA 3.0
2011-07-10T17:20:26.837Z
You could also mention "anti-hierarchy" theorems, that is, dichotomy theorems. Dichotomy theorems could probably get a whole survey unto themselves, but probably they should at least be mentioned alongside something like Ladner's Theorem.
Joshua Grochow
CC BY-SA 3.0
2012-11-07T21:55:14.340Z
Are you asking only about hierarchies of classes of problems? There is also the concept of "hierarchy of tests", see http://arxiv.org/abs/quant-ph/0308032, for instance.
Alessandro Cosentino
CC BY-SA 3.0
2012-12-06T09:37:13.933Z
Yes, only complexity class hierarchies are considered. Even limited to those, there are quite many to gather information in.
chazisop
<cc.complexity-theory><reference-request><big-list><survey><hierarchy-theorems>
What hierarchies and/or hierarchy theorems do you know?
chazisop
# What hierarchies and/or hierarchy theorems do you know?

(Asked by: username_0 on 2011-07-10)

I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, from theology and sociology to biology and chemistry. Seeing that the amount of information is vast, I hope that I could ask for some help by this community. Of course, I don't want you to do a bibliographic search for me, but rather I am asking for two kinds of information:

1. Hierarchies and hierarchy theorems that are the result of your work or the work of your colleagues or other people you are familiar with and you think that are not that well known. This could be for example a hierarchy theorem for an obscure computation model that you're interested in or a hierarchy of specific classes, e.g. related with game theory.
2. Hierarchies and hierarchy theorems that you deem absolutely necessary to be included in a survey of this kind. This would probably be known to me already, but it would be useful to see what hierarchies you consider more important and why. This could be that of the kind "I deem $PH$ very important because without it we wouldn't be able to do this kind of research" or "Although not so well known, in logic-based TCS we constantly use this hierarchy and I deem it an important tool." . And yes I do believe that people from logic have a lot of hierarchies to mention, however keep in mind we are talking about hierarchies of problems.

I will keep an updated list here:

* $DTIME$ Hierarchy
* $NTIME$ Hierarchy
* $SPACE$ Hierarchy
* Arithmetical (also known as Kleene) Hierarchy
* Hyperarithmetical Hierarchy
* Analytical Hierarchy
* Chomsky
  Hierarchy
* Grzegorczyk hierarchy
  and the related: Wainer hierarchy
  (fast-growing) , Hardy hierarchy  
  (slow-growing) and the Veblen
  hierarchy
* Ritchie's hierarchy
* Axt's hierarchy (as defined in [Axt63](https://onlinelibrary.wiley.com/doi/10.1002/malq.19630090106/abstract))
* The Loop Hierarchy (defined in [MR67](https://www.google.com/url?sa=t&source=web&cd=1&ved=0CBgQFjAA&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9311&rep=rep1&type=pdf&rct=j&q=%22the%20complexity%20of%20loop%20programs%22&ei=U5IpTqznI46q-ga068C-Bg&usg=AFQjCNEX1Eg1Cl4IRfhAeiOtyvxRuttJdQ&sig2=PPOj0_BQFyEJt9tZ890bAw&cad=rja))
* $NC$ ($AC$,$ACC$) Hierarchy
* The depth hierarchy, as defined in [Sipser83](https://dx.doi.org/10.1145/800061.808733)
* Polynomial Hierarchy ($PH$) and the less refined Meyer-Stockmeyer hierarchy (no dinstinction between quantifiers)
* Exponential Hierarchy ($ELEMENTARY$)
* $NP$-Intermediate hierarchy
  (Ladner's theorem)
* The not-so-sturdy $AM$ (Arthur-Merlin)
* The $W$ (Nondeterministic Fixed-Parameter) hierarchy and the related Alternating W hierarchy ($AW$-hierarchy) and $W^{\*}$-hierarchy (W with Parameter-Dependent Depth)
* Counting Hierarchy
* Fourier Hierarchy
* Boolean Hierarchy (over $NP$) , also equal to the Query Hierarchy (over $NP$)
* Hierarchies for property testing, as seen in [GoldreichKNR09](https://doi.org/10.1007/978-3-642-03685-9_38)
* The dot-depth hierarchy of star-free regular languages
* $BP\_{d}(P)$ : The classes solvable by polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times, form a hierarchy for different values of $d$
* The time hierarchy for Circuit Complexity
* The polynomial hierarchy in communication complexity

Note: If you do not want to be mentioned exclusively, please say so. As a rule of thumb, I will mention both the community and also the specific person that brings new information to light.

**Tags:** cc.complexity-theory, reference-request, big-list, survey, hierarchy-theorems
> **Comments:**
> **username_1**: This looks very much like a Community Wiki question. Shall I convert it?  
> **username_2**: Ladner's theorem can be generalized to get infinite hierarchies between other classes (assuming they are different) such as between **P** and **P^#P**.  
> **username_0**: @Dave Clarke please do, I guess I missed hitting that checkbox!  
> **username_3**: You could also mention "anti-hierarchy" theorems, that is, dichotomy theorems. Dichotomy theorems could probably get a whole survey unto themselves, but probably they should at least be mentioned alongside something like Ladner's Theorem.  
> **username_4**: Are you asking only about hierarchies of classes of problems? There is also the concept of "hierarchy of tests", see http://arxiv.org/abs/quant-ph/0308032, for instance.  
> **username_0**: Yes, only complexity class hierarchies are considered. Even limited to those, there are quite many to gather information in.  

---

## 23 answers

### Answer by username_5 on 2011-07-11. Score: 22

The Fourier Hierarchy as defined in "[Yaoyun Shi, Quantum and classical tradeoffs](http://www.sciencedirect.com/science/article/pii/S0304397505001878)."

From the [complexity zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo:F#fh):

> $\mathsf{FH}\_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with $k$ levels of Hadamard gates and all other gates preserving the computational basis.
>
> * $\mathsf{FH}\_0 = \mathsf{P}$
> * $\mathsf{FH}\_1 = \mathsf{BPP}$
> * $\mathsf{FH}\_2$ contains factoring because of [Kitaev's phase estimation algorithm](https://people.eecs.berkeley.edu/~vazirani/s09quantum/notes/lecture6.pdf).
>
> It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, $\mathsf{FH}\_k$ is strictly contained in $\mathsf{FH}\_{k+1}$).


---

### Answer by username_6 on 2011-07-10. Score: 20

-- Along the lines of "anti-hierarchies", [Borodin's gap theorem](http://en.wikipedia.org/wiki/Gap_theorem) might be worth mentioning.

> **Theorem.** For every total computable function $f : {\mathbb N} \rightarrow {\mathbb N}$ such that $f(n) = \Omega(n)$, there is a total computable $g : {\mathbb N} \rightarrow {\mathbb N}$ such that ${\sf TIME}[g(n)] = {\sf TIME}[f(g(n))]$.

This would contradict the time hierarchy theorem except that $g$ is not time constructable (indeed this is why we must have constructability assumptions in the statements of most complexity hierarchies).

-- There are also interesting strengthenings of the usual time hierarchies, such as:

$${\sf TIME}[n^k] \not\subseteq i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$$

(there are problems in time $n^k$ cannot be successfully solved by any time $n^{k-1}$ time machine using $n-\log n$ bits of advice, even for on just infinitely many input lengths). The proof is easy: let $\{M\_i\}$ list the $n^{k-1}$ time machines that take $n-\log n$ bits of advice as a second input. Define $M'(x)$ which splits $x$ into $x=yz$ where $|z|=\log |x|$, runs $M\_z(x,y)$, and outputs the opposite answer. Then $L(M') \notin i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$.

-- The lack of known time hierarchies in certain situations should be considered (as open problems). For example, is ${\sf BPTIME}[n] = {\sf BPP}$?

> **Comments:**
> **username_7**: Is it $\mathsf{TIME}[g(n)] = \mathsf{TIME}[f(g(n))]$? otherwise the statement is not interesting: just choose $g(n) = n$.  
> **username_8**: @Sasho, it appears so. The statement of Borodin's gap theorem (via the link) says as much.  

---

### Answer by username_3 on 2011-07-10. Score: 18

Sipser showed a depth hierarchy within $AC^0$, that is, that depth $d+1$ circuits of poly size are more powerful than depth $d$ circuits of poly size:

Sipser, M. [Borel sets and circuit complexity](http://dx.doi.org/10.1145/800061.808733). STOC 1983.


---

### Answer by username_9 on 2011-07-10. Score: 18

The Complexity Zoo gives you some [hierarchies](http://qwiki.stanford.edu/index.php/Complexity_Zoo:List_of_Hierarchies). Amongst them, the Counting Hierarchy and the Boolean Hierarchy were not already cited.

**[EDIT]** To make my answer more informative, a quick definition of the Counting Hierarchy.

* ${\sf C\_0P} = {\sf P}$
* ${\sf C\_1P} = {\sf PP}$
* ${\sf C\_{k+1}P} = {\sf PP^{C\_kP}}$

Then, as for the polynomial hierarchy, $\sf CH$ is defined as $\bigcup\_k {\sf C\_kP}$.

The counting hierarchy was defined by Wagner [Wag86]. Links to the theory of threshold circuits were discovered by Allender & Wagner [AW93]. Much more recently, Bürgisser [Bür09] also used the counting hierarchy to relate Valiant's model to the $\tau$-conjecture of Shub and Smale. In particular, he proved that the $\tau$-conjecture implies a superpolynomial lower bound for the permanent.

**[Wag86]** K.W. Wagner. [The complexity of combinatorial problems with succinct input representation](https://link.springer.com/article/10.1007/BF00289117). *Acta Mathematica* 23(3), 325-356, 1986.  
**[AW93]** E. Allender & K.W. Wagner. [Counting hierarchies: polynomial time and constant-depth circuits](https://www.worldscientific.com/doi/abs/10.1142/9789812794499_0035). *Current Trends in Computer Science*, 469-483, 1993.  
**[Bür09]** P. Bürgisser. [On defining integers and proving arithmetic circuit lower bound](https://www3.math.tu-berlin.de/algebra/work/6dich.pdf). *Computational Complexity* 18(1), 81-103, 2009.


---

### Answer by username_10 on 2011-07-10. Score: 18

Goldreich et. al. have hierarchy theorems for property testing:

* Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
  [Hierarchy Theorems for Property Testing.
  Property Testing](http://www.wisdom.weizmann.ac.il/~oded/PDF/testHT2.pdf), Lecture Notes in Computer Science, Vol. 6390, pp. 289-294, Springer, 2010.

Also on the [ECCC](http://eccc.hpi-web.de/report/2008/097/).

> **Comments:**
> **username_11**: [here](http://arxiv.org/abs/quant-ph/0201117) it is shown that most properties require $\Omega(n)$ queries in the quantum model. This can be plugged into the proof of the answer's hierarchy theorem to show that it holds for quantum property testing, too. (In fact for any natural computational model with at least one property that requires $\Omega(g(n))$ queries to test, and any computable $f(n) \in O(g(n))$ you have properties which is testable in $\Theta(f(n))$ queries).  

---

### Answer by username_2 on 2011-07-10. Score: 12

[Dieter van Melkebeek](http://pages.cs.wisc.edu/~dieter/) and coauthors have time and space hierarchies for semantic models with advice, including randomization.

* Dieter van Melkebeek, Konstantin Pervyshev: [A Generic Time Hierarchy with One Bit of Advice](http://pages.cs.wisc.edu/~dieter/Papers/t-hierarchy-ccc06.ps). Computational Complexity 16(2): 139-179 (2007)
* Jeff Kinne, Dieter van Melkebeek: [Space Hierarchy Results for Randomized and other Semantic Models](http://pages.cs.wisc.edu/~dieter/Papers/s-hierarchy-full.pdf). Computational Complexity 19(3): 423-475 (2010)


---

### Answer by username_12 on 2011-07-11. Score: 11

Here are more hierarchies for semantic classes with advice. Specifically, for ZPTIME and RTIME.

Lance Fortnow, Rahul Santhanam, Luca Trevisan. [Hierarchies for Semantic Clases](http://portal.acm.org/citation.cfm?id=1060590.1060642). In STOC'05.


---

### Answer by username_13 on 2011-07-10. Score: 11

There is the Zheng-Weihrauch hierarchy for real numbers

X. Zheng and K. Weihrauch. [The arithmetical hierarchy of real numbers](https://link.springer.com/chapter/10.1007/3-540-48340-3_3). Mathematical Logic Quarterly.Vol. 47(2001), no.1 51 - 65.


---

### Answer by username_14 on 2012-05-28. Score: 10

There is a class $\mathsf{D}$, defined in a 1975 paper by L. Adelman and K. Manders, which is a diophantine analogue of the class $\mathsf{NP}$.
A language $L$ is contained in $\mathsf{D}$ iff there exists a polynomial $P$ such that
$$x \in L \Leftrightarrow \exists y\_1, \dots y\_n < poly(|x|) \colon ~P(x, y\_1,\dots, y\_n) = 0.$$
Whether $\mathsf{D}$ equals $\mathsf{NP}$ is an open problem. This equality would show connections between number theory and computer science.

There is a diophantine analogue of the polynomial hierarchy, called the "diophantine hierarchy". The polynomial and diophantine hierarchies are intertwined:
$$\forall i \ge 1,~\Sigma^i D \subset \Sigma^i P \subset \Sigma^{i + 1}D$$

> **Comments:**
> **username_15**: Do you mean http://doi.ieeecomputersociety.org/10.1109/SFCS.1975.9 or http://doi.ieeecomputersociety.org/10.1109/SFCS.1976.13 ?  
> **username_16**: $D$ is defined in the second one ("Diophantine Complexity").  

---

### Answer by username_15 on 2011-07-12. Score: 10

Another strict hierarchy: branching programs which only test each bit a limited number of times. The more tests are allowed, the larger the class of branching programs.
Usually the branching programs are also restricted to polynomial size.
BPd(P) is the class of polynomial size branching programs that may test each bit up to $d$ times.

[L/poly](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#l.2Fpoly) is the union of [BPd(P)](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bpdp) over all *d*, while BPd-1(P) $\subsetneq$ BPd(P) for every *d*.


---

### Answer by username_17 on 2011-07-25. Score: 9

In [parameterized complexity](https://en.wikipedia.org/wiki/Parameterized_complexity) theory there are several hierarchies although only the already mentioned $\mathsf{W}$-hierarchy appears often in publications. Others are:

* $\mathsf{A}$-hierarchy
* $\mathsf{AW}$-hierarchy
* $\mathsf{EW}$-hierarchy
* $\mathsf{LOG}$-hierarchy
* $\mathsf{M}$-hierarchy
* $\mathsf{S}$-hierarchy
* $\mathsf{W^∗}$-hierarchy
* $\mathsf{W^{func}}$-hierarchy

They are all described in [Parameterized complexity theory, Flum and Grohe, Birkhäuser, 2006](https://www.springer.com/gp/book/9783540299523).


---

### Answer by username_18 on 2011-07-11. Score: 8

Not sure if this fits your criteria, but there is the [dot-depth hierarchy](http://www.sciencedirect.com/science/article/pii/0022000078900491) of star-free regular languages.


---

### Answer by username_20 on 2011-07-11. Score: 7

The hierarchy for circuit size, see
[previous question](https://cstheory.stackexchange.com/questions/5110/time-hierarchy-theorem-for-circuit-complexity).


---

### Answer by username_12 on 2014-02-05. Score: 6

Here is a [new hierarchy for context-free languages](http://arxiv.org/abs/1303.1717) by Tomoyuki Yamakami.

He introduces an oracle mechanism in nondeterministic pushdown automata and notions of Turing and many-one reducibilities. Then a new hierarchy is constructed for Context-free languages (CFL) similar to the polynomial hierarchy. For example, $CFL$, $CFL^{CFL}$, etc. The interesting part of all this is that a collapse in the CFL hierarchy occurs if and only if the polynomial hierarchy collapses.


---

### Answer by username_19 on 2014-02-02. Score: 6

The theory of regular languages of infinite trees gave rise to several hierarchies, that are currently studied, with many questions that are still open.

When using automata on infinite trees, the parity condition (or Mostowski condition) is of special interest, because non-deterministic parity automata can express all regular languages of infinite trees, and the structure of the acceptance condition is simpler than others like Rabin or Müller.

Every parity automaton has a *rank* $[i,j]$ where $i\in\{0,1\}$ and $i\leq j$, describing the structure of the acceptance condition. Therefore, if a language $L$ is recognizable by a (det/ND/alt) automaton of rank $[i,j]$ we say that $L$ belongs to the $[i,j]$-level of the (respectively):

* deterministic Mostowski hierarchy (not all regular languages)
* nondeterministic Mostowski hierarchy
* alternating Mostowski hierarchy

The level $\Sigma\_2\cap \Pi\_2$ of the alternating hierarchy (i.e $L$ is both Büchi and co-Büchi definable) corresponds to the *weak level* and is characterised by weak alternating automata, that give themselves rise to a hierarchy:

* weak index hierarchy (not all regular languages)

For all these hierarchies (except the deterministic one), the decidability of membership in a level for a given regular language $L$ is an open problem. The links between these hierarchies and topological classifications (also called Wadge hierarchy and Borel hierarchy) also pose several open problems. For instance it is conjectured that the weak index hierarchy and the Borel hierarchy coincide. All these hierarchies are known to be strict, and some special cases of deciding the level (especially the low levels, or with input deterministic automaton) have been recently solved.


---

### Answer by username_21 on 2011-08-06. Score: 5

There are hierarchies in propositional proof complexity similar to those in circuit complexity. E.g. $G\_i$ propositional roof systems are similar to $\mathsf{PH}$, C-Frege proof systems for $C \subset \mathsf{P}$ are similar to circuit complexity classes $C$, and so on.

There are also hierarchies in bounded arithmetics, e.g. $\mathsf{S^i\_j}$ theories, etc.


---

### Answer by username_22 on 2019-07-01. Score: 3

Elaborating on one of the bullet points mentioned by the OP (GoldreichKNR09): there are several hierarchy theorems in property testing and proofs of proximity, relating to the query complexity, the adaptivity, or the testability with regard to number of rounds (for proofs of proximity). See, e.g.,

* *Hierarchy Theorems for Property Testing*, Oded Goldreich, Michael KrivelevichIlan Newman, and Eyal Rozenberg, 2012.
  <https://link.springer.com/article/10.1007/s00037-011-0022-4> **[mentioned by the OP]**
* *A Hierarchy Theorem for Interactive Proofs of Proximity*, Tom Gur and Ron Rothblum, 2017.
  <http://drops.dagstuhl.de/opus/volltexte/2017/8153/>
* *Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity*, Oded Goldreich, 2018.
  <https://eccc.weizmann.ac.il/report/2018/098/>
* *An adaptivity hierarchy theorem for property testing*, Clément Canonne and Tom Gur, 2018.
  <https://link.springer.com/article/10.1007%2Fs00037-018-0168-4>

> **Comments:**
> **username_22**: Pointer to [this answer](https://cstheory.stackexchange.com/a/7305/13319), which focuses on the first one (GoldreichKNR09).  

---

### Answer by username_18 on 2019-09-13. Score: 3

From [this question on cs.stackexchange](https://cs.stackexchange.com/questions/114676/planar-regular-languages), I became aware of the **genus hierarchy of regular languages**. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper.

1. Bonfante, Guillaume, and Florian Deloup. "[The genus of regular languages.](https://arxiv.org/pdf/1301.4981.pdf)" Mathematical Structures in Computer Science 28.1 (2018): 14-44.


---

### Answer by username_23 on 2022-07-28. Score: 2

Lasserre Hierarchy: *An* Hierarchy of progressively stronger (i.e., tighter, in the sense of integrality gaps) SDP relaxations of fractional polytopes

* J. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1
  programs. In IPCO, pages 293–303, 2001.
* J. Lasserre. Global optimization with polynomials and the problem of
  moments. SIAM Journal on Optimization, 11(3):796–817, 2001.

There are other hierarchies of that kind (Sherali-Adams, Lovasz-Schrijver etc.) but they are all subsumed by Lasserre.


---

### Answer by username_24 on 2012-05-29. Score: 2

Counting Polynomial Hierarchy, #PH for short. First level is #P then #NP... etc.


---

### Answer by username_25 on 2016-02-23. Score: 1

The Polynomial Hierarchy in communication complexity as defined by Babai, Frankl, and Simon (see [the original paper here](http://dl.acm.org/citation.cfm?id=1382962) and without the paywall [here](http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/papers/BabaiFS1986.pdf)). The significance of this hierarchy is hard to overestimate. First of all, the disjointness function was introduced by BFS in the same paper that introduced the hierarchy, and the disjointness appeared quite naturally as a coNP$^{cc}$-complete problem. As you know, the disjointness is **THE** function in communication complexity. Secondly, proving lower bounds against the polynomial hierarchy in communication complexity is a major open problem with important implications in other areas of TCS (for example, see [this paper](http://eccc.hpi-web.de/report/2015/049/) and references therein).

> **Comments:**
> **username_0**: Thanks for the addition, I edited your comment to make clear coNP refers to communication complexity (I know this is commonly dropped in the communication complexity community to avoid notation clutter).  

---

### Answer by username_26 on 2019-07-01. Score: 1

Consider the Unambiguous Polynomial Hierarchy, [reference here](https://arxiv.org/pdf/cs/9907033.pdf), original reference here for  [the unambiguous polynomial hierarchy](https://ieeexplore.ieee.org/document/315812?arnumber=315812)(paywalled). While studying the Boolean hierarchy **BH**, and classes such as **$D\_{p}$** which have nice results related to closure, and set differences we can explore connections to unambiguous computation.

As authors(in original reference) state, the classes $NC^{k}$, and $AC^{k}$ give results related to $P$, and $PSPACE$. With an unambiguous circuit, they could characterize $P$ differently. Also, related to the above hierarchy is the Promise Unambiguous Hierarchy. Lowness results for the Unambiguous Polynomial Hierarchy- "if there is a sparse Turing Completer set for $UP$, hierarchy collapses to lower levels, or into the Promise Unambiguous Case".

Related for further study of Boolean connectives, and Graph Isomorphism are  [the Low, and High Hierarchies](https://linkinghub.elsevier.com/retrieve/pii/0022000083900272), also [wikipedia reference](https://en.wikipedia.org/wiki/Low_and_high_hierarchies).


---

### Answer by username_27 on 2019-09-25. Score: 0

More on the obscure side: My second order heirarchy theorem for fixed point logics in finite model theory. See [Yet Another Hierarchy Theorem](http://www.maxky.de/papers/unafp.pdf).


---

