Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

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.

share|improve this question
2  
This looks very much like a Community Wiki question. Shall I convert it? –  Dave Clarke Jul 10 '11 at 12:42
    
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 Jul 10 '11 at 12:54
    
@Dave Clarke please do, I guess I missed hitting that checkbox! –  chazisop Jul 10 '11 at 13:14
13  
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 Jul 10 '11 at 17:20
1  
Yes, only complexity class hierarchies are considered. Even limited to those, there are quite many to gather information in. –  chazisop Dec 6 '12 at 9:37
show 1 more comment

17 Answers 17

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

From the complexity zoo:

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

  • FH0 = P
  • FH1 = BPP
  • FH2 contains factoring because of Kitaev's phase estimation algorithm

It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, FHk is strictly contained in FHk+1).

share|improve this answer
add comment

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

  • Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Hierarchy Theorems for Property Testing. Property Testing, Lecture Notes in Computer Science, Vol. 6390, pp. 289-294, Springer, 2010.

Also on the ECCC.

share|improve this answer
    
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). –  Artem Kaznatcheev Jul 13 '11 at 11:00
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
2  
Is it $\mathsf{TIME}[g(n)] = \mathsf{TIME}[f(g(n))]$? otherwise the statement is not interesting: just choose $g(n) = n$. –  Sasho Nikolov Jul 14 '11 at 3:31
    
@Sasho, it appears so. The statement of Borodin's gap theorem (via the link) says as much. –  Daniel Apon Jul 23 '11 at 16:05
    
Thanks for pointing that out! –  Ryan Williams Aug 6 '11 at 16:08
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

L/poly is the union of BPd(P) over all d, while BPd(P) strictly contains BPd-1(P) for $d \gt 1$.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

The hierarchy for circuit size, see previous question.

share|improve this answer
add comment

In parameterized complexity theory there are several hierarchies. However only the already mentioned W-hierarchy appears often in publications. Others are:

  • the A-hierarchy
  • the AW-hierarchy
  • EW-hierarchy
  • LOG-hierarchy
  • M-hierarchy
  • S-hierarchy
  • $W^∗$-hierarchy
  • $W^{func}$-hierarchy

They are all described in Parameterized complexity theory, Flum and Grohe, Birkhäuser, 2006.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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