42
$\begingroup$

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)
  • The Loop Hierarchy (defined in MR67)

  • $NC$ ($AC$,$ACC$) Hierarchy

  • The depth hierarchy, as defined in Sipser83
  • 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
  • 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.

$\endgroup$
  • 2
    $\begingroup$ This looks very much like a Community Wiki question. Shall I convert it? $\endgroup$ – Dave Clarke Jul 10 '11 at 12:42
  • $\begingroup$ Ladner's theorem can be generalized to get infinite hierarchies between other classes (assuming they are different) such as between P and P^#P. $\endgroup$ – Tyson Williams Jul 10 '11 at 12:54
  • 13
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Jul 10 '11 at 17:20
  • 1
    $\begingroup$ Are you asking only about hierarchies of classes of problems? There is also the concept of "hierarchy of tests", see arxiv.org/abs/quant-ph/0308032, for instance. $\endgroup$ – Alessandro Cosentino Nov 7 '12 at 21:55
  • 1
    $\begingroup$ Yes, only complexity class hierarchies are considered. Even limited to those, there are quite many to gather information in. $\endgroup$ – chazisop Dec 6 '12 at 9:37

22 Answers 22

21
$\begingroup$

The Fourier Hierarchy as defined in "Yaoyun Shi, Quantum and classical tradeoffs."

From the complexity zoo:

$\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.

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}$).

$\endgroup$
18
$\begingroup$

-- Along the lines of "anti-hierarchies", Borodin's 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}$?

$\endgroup$
  • 2
    $\begingroup$ Is it $\mathsf{TIME}[g(n)] = \mathsf{TIME}[f(g(n))]$? otherwise the statement is not interesting: just choose $g(n) = n$. $\endgroup$ – Sasho Nikolov Jul 14 '11 at 3:31
  • $\begingroup$ @Sasho, it appears so. The statement of Borodin's gap theorem (via the link) says as much. $\endgroup$ – Daniel Apon Jul 23 '11 at 16:05
16
$\begingroup$

The Complexity Zoo gives you some 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. Acta Mathematica 23(3), 325-356, 1986.
[AW93] E. Allender & K.W. Wagner. Counting hierarchies: polynomial time and constant-depth circuits. Current Trends in Computer Science, 469-483, 1993.
[Bür09] P. Bürgisser. On defining integers and proving arithmetic circuit lower bound. Computational Complexity 18(1), 81-103, 2009.

$\endgroup$
16
$\begingroup$

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

Also on the ECCC.

$\endgroup$
  • $\begingroup$ here 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). $\endgroup$ – Artem Kaznatcheev Jul 13 '11 at 11:00
15
$\begingroup$

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. STOC 1983.

$\endgroup$
11
$\begingroup$

Dieter van Melkebeek and coauthors have time and space hierarchies for semantic models with advice, including randomization.

$\endgroup$
10
$\begingroup$

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

Lance Fortnow, Rahul Santhanam, Luca Trevisan. Hierarchies for Semantic Clases. In STOC'05.

$\endgroup$
10
$\begingroup$

There is the Zheng-Weihrauch hierarchy for real numbers

X. Zheng and K. Weihrauch. The arithmetical hierarchy of real numbers. Mathematical Logic Quarterly.Vol. 47(2001), no.1 51 - 65.

$\endgroup$
9
$\begingroup$

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$$

$\endgroup$
8
$\begingroup$

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 is the union of BPd(P) over all d, while BPd-1(P) $\subsetneq$ BPd(P) for every d.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

Not sure if this fits your criteria, but there is the dot-depth hierarchy of star-free regular languages.

$\endgroup$
6
$\begingroup$

The hierarchy for circuit size, see previous question.

$\endgroup$
5
$\begingroup$

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 ininite 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 posed 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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Here is a new hierarchy for context-free languages 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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Pointer to this answer, which focuses on the first one (GoldreichKNR09). $\endgroup$ – Clement C. Jul 1 at 22:09
3
$\begingroup$

From this question on cs.stackexchange, 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." Mathematical Structures in Computer Science 28.1 (2018): 14-44.
$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

The Polynomial Hierarchy in communication complexity as defined by Babai, Frankl, and Simon (see the original paper here and without the paywall here). 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 and references therein).

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – chazisop Feb 23 '16 at 2:48
1
$\begingroup$

Consider the Unambiguous Polynomial Hierarchy, reference here, original reference here for the unambiguous polynomial hierarchy(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, also wikipedia reference.

$\endgroup$
0
$\begingroup$

More on the obscure side: My second order heirarchy theorem for fixed point logics in finite model theory. See Yet Another Hierarchy Theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.