Examples of collapsing hierarchies

Question

Are there interesting examples of "collapsing hierarchies" in computer science?

The formal definition of a hierarchy here would be a class of languages/problems/objects which is parametrized by a partially ordered set. But I am of course looking for an at least somewhat "natural" hierachy, where the parameter represents some type of resource. I am particularly interested in hierarchies where the parameter space is $\mathbb{N}$ or the $\Sigma_i/\Pi_i$ ladder. Some examples are

• the polynomial hierarchy (counting alternations),
• the lightface hierarchy (same),
• $NC^i$ and $AC^i$,
• various ways to associate languages to $k$-headed finite-state automata (as $k$ grows).

I am also happy with more complicated parameter spaces such as polynomial time languages parametrized by their time-complexity or space-complexity, if you know interesting collapsing results for them.

By collapsing I simply mean that some level of the hierarchy already contains all elements of the hierarchy. In all natural cases I can think of, either we know hierarchy does not collapse or we don't know whether it collapses. I would like to know some examples of hierarchies that do collapse. The hierarchy should be "natural", and I would prefer an example where the collapse does not happen "on the first level".

I did not carefully check that none of the hierarchies listed in What hierarchies and/or hierarchy theorems do you know? collapse, but at least it is not known to collapse for any of the ones I was familiar with, or for which this was mentioned in the answers.

Answer 1

The analogue of the $\mathsf{NC}$ hierarchy for algebraic circuits is known to collapse to the second level. That is, algebraic circuits of size $n^{O(1)}$ computing a polynomial of degree $n^{O(1)}$ can be rebalanced to have depth $O(\log^2 n)$ while only increasing the size by a polynomial factor. This is due to Valiant, Skyum, Berkowitz, and Rackoff. It is open whether $\mathsf{NC}^1 \stackrel{?}{=} \mathsf{NC}^2$ in this setting, but I believe the popular opinion is that $\mathsf{NC}^1 \neq \mathsf{NC}^2$ here.

If one further restricts to syntactically multilinear algebraic circuits, then we in fact know $\mathsf{NC}^0 \subsetneq \mathsf{NC}^1 \subsetneq \mathsf{NC}^2 = \mathsf{NC}$ unconditionally. The fact that $\mathsf{NC}^1 \subsetneq \mathsf{NC}^2$ is due to Raz, and the fact that $\mathsf{NC}^2 = \mathsf{NC}$ is due to Raz and Yehudayoff.

Raz, Ran, Separation of multilinear circuit and formula size, Theory Comput. 2, Paper No. 6, 121-135 (2006). ZBL1213.68301.

Raz, Ran; Yehudayoff, Amir, Balancing syntactically multilinear arithmetic circuits, Comput. Complexity 17, No. 4, 515-535 (2008). ZBL1188.68367.

Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C., Fast parallel computation of polynomials using few processors, SIAM J. Comput. 12, 641-644 (1983). ZBL0524.68028.

Answer 2

The AM hierarchy (constant-round interactive proofs) collapses to AM (Babai-Moran '88), but we don't yet know whether NP=MA=AM.

Answer 3

When I was in graduate school, I once presented for a class a paper from a STOC conference (mid-80's) entitled "The Strong Exponential Hierarchy Collapses".

Answer 4

Interesting result from Quantum Computing, though, If it fits into your requirements of what hierarchies you are looking at, is at discretion. The QMA hierarchy collapse result of Harrow, Montanaro where QMA(2) =QMA(k) for k >= 2.

More collapsing results:

The $PL$ (Probabilistic Logspace) hierarchy collapses, ie $ PLH$ = $PL$. See paper here. . The relativization model used is the Russo-Simon-Tompa relativization model. The choice of relativization is noted in the definition of the hierarchy.

Another collapse result related to the counting classes, and "exact" Arithmetic Hierarchies, reference here. The collapse is to the third level of the $AC^{0}$ -hierarchy.

Answer 5

Barrington’s theorem: if $\def\bp{\mathrm{BP}}\bp_k$ denotes the class of languages computable by polynomial-size width-$k$ branching programs, we have $$\bp_1\subsetneq\bp_2\subsetneq\bp_3\subseteq\bp_4\subseteq\bp_5=\bigcup_{k\in\mathrm N}\bp_k=\mathrm{NC}^1.$$ Note that $\bp_4\subseteq\mathrm{AC}^0[6]$, hence likely $\bp_4\subsetneq\bp_5$.

Answer 6

k-SAT collapses at 3, of course.

Answer 7

From computability theory we have the Ershov hierarchy, or rather its "naive linearization."

The goal of the Ershov hierarchy is to analyze the $\Delta^0_2$ sets - that is, the sets computable from the halting problem $\emptyset'$. The starting point is to generalize the c.e. sets:

• A set is $1$-c.e. iff it is c.e., and a set is co-$1$-c.e. if it is co-c.e.

• A set is $(n+1)$-c.e. iff it is of the form $A\setminus B$ for $A$ $n$-c.e. and $B$ c.e., and a set is co-$(n+1)$-c.e. if its complement is $(n+1)$-c.e.

This is all nice and simple, but it doesn't finish the job: there are $\Delta^0_2$ sets which are not Turing equivalent to any $n$-c.e. set for any $n\in\mathbb{N}$. To get all the $\Delta^0_2$ sets we need to go into the transfinite. The basic idea is that a set $A$ is at the $l$th level of the hierarchy for $l$ a computable well-ordering if there is a computable "approximation" function $f(x,s)$ and a computable "clock" function $g(x,s)$ such that:

• $\lim_{s\rightarrow\infty} f(x,s)=A(x)$ (so $f$ yields a $\Delta^0_2$ description of $A$), and

• $g:\mathbb{N}^2\rightarrow l$ is nonincreaning and satisfies $$f(x,s)\not=f(x,s+1)\implies g(x,s)>_l g(x,s+1).$$

Since $l$ is well-ordered, the clock $g$ eventually stops "ticking" and so our approximator $f$ can only change its mind finitely many times. So all of these sets are limit computable, hence $\le_T \emptyset'$.

For the precise definition of the Ershov hierarchy see here

The problem - as often happens with such ideas - is that in the definitions of $l$-c.e.ness and co-$l$-c.e.ness the object $l$ is not an ordinal but rather a specific presentation of an ordinal: we can have two computable well-orderings $l_0,l_1$ of the same ordertype such that there is an $l_0$-c.e. set which is not $l_1$-c.e. So really, the Ershov "hierarchy" isn't a linear hierarchy at all: rather than being indexed by ordinals $<\omega_1^{CK}$ it's indexed by ordinal notations.

A natural hope at this point is that we can "linearize" things: for $\alpha$ an ordinal $<\omega_1^{CK}$, say that $A$ is optimally $\alpha$-c.e. iff $A$ is $l$-c.e. for some computable well-ordering $l$ of ordertype $\alpha$. This trivially gets us a genuine linear hierarchy, since the ordinals themselves are linearly ordered. However, this new hierarchy collapses: every $\Delta^0_2$ set is $l$-c.e. for some presentation $l$ of $\omega^2$, so the "optimal Ershov hierarchy" collapses at level $\omega^2$.

---

What makes this particularly interesting is its contrast with a seemingly-similar construction: the hyperarithmetic hierarchy. Here again we have a "hierarchy" indexed by ordinal notations: for a well-ordering $l$ of $\mathbb{N}$ (computable or not!) there is a natural way to iterate the Turing jump along $l$, and the hyperarithmetic sets are those computable from some iterate of the jump along a computable well-ordering starting with $\emptyset$. So this superficially has the same flavor as the Ershov hierarchy.

But now we have a very surprising, in light of the above, well-definedness phenomenon: if $l_0,l_1$ are computable well-orderings of $\mathbb{N}$ with the same ordertype $\alpha<\omega_1^{CK}$, then $X^{(l_0)}\equiv_TX^{(l_1)}$ for every set $X$. Consequently we get an increasing sequence of Turing degrees of length $\omega_1^{CK}$, such that the hyperarithmetic sets are exactly the sets computable from some member of this sequence.

Sacks' book gives a good treatment of this topic.

Answer 8

The parity acceptance condition for automata on infinite words induces a hierarchy of type $\Sigma_i/\Pi_i$, noted $[0,i]$ and $[1,i+1]$ with $i\in\mathbb N$. The parity condition of level $[a,b]$ works as follows: each state is labelled with an integer in $[a,b]$, and an infinite run is accepting iff the largest integer appearing infinitely often is even.

For nondeterministic automata, the hierarchy collapses at the level $[1,2]$, meaning that every regular language of infinite words can be accepted by a nondeterministic $[1,2]$-automaton, also known as Büchi automata.

For deterministic automata, the hierarchy does not collapse: for every level you can find regular languages which need at least this level of the parity hierarchy for a deterministic recognizer.

Answer 9

Recall that for any prime $p$, the modulo-$p$ counting hierarchy $\def\modph#1{\mathrm{Mod}_{#1}\mathrm{PH}}\modph p$ is defined as the smallest class of languages such that

• $\mathrm{NP}^{\modph p}\let\sset\subseteq\sset\modph p$,
• $\oplus_p\mathrm P^{\modph p}\sset\modph p$.

Toda’s theorem ensures that it collapses to $$\modph p=\mathrm{BP}\cdot\oplus_p\mathrm P=\exists\forall\cdot\oplus_p\mathrm P=\forall\exists\cdot\oplus_p\mathrm P.$$ Depending on how exactly you count it, this is around the second or third level of the hierarchy.

Answer 10

With three counters (or any larger amount) you can recognize precisely the recursively enumerable sets $A \subset \mathbb{N}$. With two counters, you cannot recognize the prime numbers or $e$th powers of natural numbers for fixed $e \geq 2$.

Two heads are already quite powerful: the sets $\{2^n \;|\; n \in A\}$ you can accept are precisely the ones where $A$ is recursively enumerable.

One head is of little interest (accepts exactly the semilinear sets).

The model: Finite state set, and as primitive operations you can check counters for zero, and increment and decrement them. The input value is initially in the first counter.

Ibarra, Oscar H.; Trân, Nicholas Q., A note on simple programs with two variables, Theor. Comput. Sci. 112, No. 2, 391-397 (1993). ZBL0785.68033.

Answer 11

Isomorphism of $d$-tensors for any $d$ reduces to isomorphism of 3-tensors. (G.-Qiao, ITCS '21).

3-Tensor Isomorphism is at least as hard as Graph Isomorphism, and seems quite a bit harder (the current best algorithm is not asymptotically better than the trivial $q^{O(n^2)}$ algorithm for $n \times n \times n$ tensors over $\mathbb{F}_q$). This seems strictly harder than isomorphism of 2-tensors=matrices, which is in $\mathsf{NC}^2$, and which in turn seems strictly harder than isomorphism of 1-tensors=vectors, which is completely trivial, as any two nonzero vectors are "isomorphic."

This is philosophically similar to the answer about k-SAT and many other NP-complete problems, such as k-coloring, k-dimensional matching, etc., but different in an interesting respect. For NP-complete problems, once you know that e.g. 3-SAT is NP-complete, you get reductions from k-SAT for all larger k simply by showing they are in NP. But the above isomorphism problems are not $\mathsf{NP}$-complete unless $\mathsf{PH}$ collapses, so one cannot use any such trick. The reduction for tensors is pretty involved.

Answer 12

While the OP indicated they do not like it as it is a collapse to the first level, I think this deserves a mention because it is probably the most prominent example of something that was originally conceived and studied as a hierarchy until it was shown to collapse:

The alternating logspace hierarchy $\Sigma_k^{\log}=\Sigma_k\text-\mathrm{SPACE}(\log n)$ collapses to $\mathrm{NL=coNL}$ by the Immerman–Szelepcsényi theorem. (It is a lesser known fact that shortly before that, it was shown to collapse to $\Sigma^{\log}_2=\Pi^{\log}_2$ by Jenner, Kirsig & Lange.)

Answer 13

The bounded (relational) width hierarchy of constraint satisfaction problem templates collapses: this was proved in Barto, Libor, The collapse of the bounded width hierarchy, J. Log. Comput. 26, No. 3, 923-943 (2016). ZBL1353.68107. The same result was also proved independently by Andrei Bulatov in an unpublished manuscript (link) around the same time.

The collapse was then sharpened in Kozik, Marcin, Weak consistency notions for all the CSPs of bounded width, Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 633-641 (2016). ZBL1401.68123. This was later sharpened further in this paper, also by Kozik.

A constraint satisfaction problem template is a finite domain $D$ of values that variables may take (such as $\{r,g,b\}$ for the $3$-coloring problem), together with a finite set of relations $\Gamma = \{R_1, R_2, ...\}$, with each $R_i$ a $k_i$-ary relation which may be described explicitly as a subset of $D^{k_i}$, that may be used to build puzzles (for the $3$-coloring problem, we would take $\Gamma = \{\ne\}$, where $\ne$ is the binary relation on $\{r,g,b\}$ corresponding to the set $\{r,g,b\}^2 \setminus \{(r,r),(g,g),(b,b)\}$). Specific puzzles built using relations from $\Gamma$ are known as "instances" of the CSP template $(D,\Gamma)$.

For a given CSP template $(D,\Gamma)$, it is natural to ask whether certain simple "local propagation" algorithms can decide every instance of $(D,\Gamma)$. The simplest "local propagation" algorithm is called arc consistency (or generalized arc consistency/hyper-arc consistency, if the relations have arity greater than $2$) - this strategy is the strategy most beginner Sudoku players use. Slightly more complex local propagation strategies are described in this wikipedia page.

The most general definition of local propagation algorithms is defined in terms of the programming language Datalog, and one can make a relatively straightforward hierarchy of canonical Datalog programs that deduce as much as they possibly can by looking at $k$ variables at a time (or, if $k$ is less than the maximum arity $k_i$ of any relation $R_i$ in $\Gamma$, we can also allow ourselves to study any set of variables that occur simultaneously within the scope of a single occurrence of a relation in the instance - this modification is necessary to treat generalized arc consistency properly).

The full bounded width hierarchy then collapses to the following few layers (each strictly contained in the next):

• the templates that can be solved by (generalized) arc consistency (one such template is HORN-SAT),
• the templates that can be solved by the basic linear programming relaxation,
• the templates that can be solved by "cycle consistency": a slight strengthening of arc-consistency which is probably familiar to more advanced Sudoku players (one such template is 2-SAT). This layer is contained within the $3$rd level of the Datalog hierarchy described above.

Anything which is not in one of those layers can simulate systems of affine-linear equations modulo a prime $p$, and thus can't be solved at any level of the bounded width hierarchy.

An example of a CSP template which is solved by the basic linear programming relaxation but is not solved by (generalized) arc-consistency can be found at the end of section 3.2 of Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar, Towards a characterization of constant-factor approximable min CSPs, Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 847-857 (2015). ZBL1371.90116.

Answer 14

Perhaps this recent result (Jan 2020) showing that MIP* = RE.