18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I am assuming this is a relatively rare phenomenon, so don't be shy if you know a really obscure example. $\endgroup$ – Ville Salo Aug 4 at 13:47
  • 5
    $\begingroup$ The alternating logspace hierarchy collapses to NL = coNL. (Even before Immerman–Szelepcsényi, it was shown to collapse to $\mathrm{L^{NL}}$.) Also, I don’t know if you’d consider it a hierarchy (though it sounds similar in spirit to your last example), but bounded width branching programs collapse to width 5. $\endgroup$ – Emil Jeřábek Aug 4 at 14:26
  • 2
    $\begingroup$ Concerning your last paragraph, this is to be expected, as once a hierarchy is known to collapse, it generally stops being called a hierarchy. $\endgroup$ – Emil Jeřábek Aug 4 at 14:31
  • $\begingroup$ Hard to answer to specific things, but here's my response: I would say NL = coNL is an example of collapse on the first level level, I would be more interested in cases where there is an actual beginning of a hierarchy (at least conjecturally), and THEN a collapse. Barrington's theorem is actually a nice example, I did not think of that one. Are there examples of hierarchies that collapsed on a level other than the first, and we subsequently stopped calling them hierachies? $\endgroup$ – Ville Salo Aug 4 at 14:52
  • 1
    $\begingroup$ Maybe Barrington's theorem is also a good example also for the last question: I would probably call it a hierarchy if it were infinite. $\endgroup$ – Ville Salo Aug 4 at 14:54

14 Answers 14

18
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very cool, I had no idea! $\endgroup$ – Ville Salo Aug 4 at 16:34
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ More explicit from the (equivalent) statement $\mbox{AM}[2] = \mbox{AM}[k]$ for $k \geq 2$, but I guess the numbering is not so popular exactly because the hierarchy collapses. (Also, maybe an unpopular opinion, but I think AM should be called AMA, I can never remember which is which.) $\endgroup$ – Ville Salo Aug 5 at 5:10
  • $\begingroup$ @VilleSalo: Remembering is why I like the "Merlin-Arthur" nomenclature better than "interactive proofs" for AM and MA. Merlin is the wizard; if Arthur goes first (AM), then Merlin can do more with the information learned from Arthur than if Merlin is forced to go before Arthur reveals his (mortal, but randomized) hand. $\endgroup$ – Joshua Grochow Aug 7 at 17:30
  • 1
    $\begingroup$ I have just memorized that AM is bigger than MA, and I deduce the literary devices, rules and wizard mnemonics from that. Maybe it's to some extent a cultural thing, I checked with someone (Finnish) who doesn't do complexity theory, and they had never heard of a "Merlin", though did guess that out of Arthur&Merlin, the latter must be the wizard. $\endgroup$ – Ville Salo Aug 8 at 6:33
  • 1
    $\begingroup$ (I'm pretty sure most people have heard of Merlin, but it's a small enough deal that you could certainly completely forget this. I've never heard the story, I've just heard of some story involving these characters.) $\endgroup$ – Ville Salo Aug 8 at 6:36
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Ok, collapse in number of Merlins in a quantum Merlin-Arthur protocol. Two Merlins suffice. $\endgroup$ – Ville Salo Aug 5 at 5:13
  • 1
    $\begingroup$ The original paper on which the exact Arithmetic Hierarchies collapse paper is based is by Allender-Beals-Ogihara (cs.rutgers.edu/~allender/papers/rank.pdf). The PP hierarchy is shown to collapse by Beigel-Fu. $\endgroup$ – SamiD Aug 8 at 23:34
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ On a related note, in the arithmetic setting, we have Ben-Or and Cleve's result that functions computable by arithmetic branching programs of width $k$ can be computed by width $3$. $\endgroup$ – Nikhil Aug 8 at 18:36
5
$\begingroup$

k-SAT collapses at 3, of course.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Good point. I'll note that both this and my counter machine answer sound like a collapse on the third level, but in both cases it is only the second interesting level. $\endgroup$ – Ville Salo Aug 5 at 12:02
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, first answer so far that is not a "collapse on the second interesting level". BUT, it is collapse at the "second interesting exponential ordinal". I don't know if that's a stretch since I don't know the proof, but it seems it means $g$ is using two counters instead of one. $\endgroup$ – Ville Salo Aug 6 at 5:24
  • $\begingroup$ I was not aware that there was a linearization issue with this, and can't help wondering if it's related in some way to the fact $\omega^2$ is the first level where you have terminal branches in the tree of computable ordinals? $\endgroup$ – Ville Salo Aug 6 at 5:25
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Isomorphism of $d$-tensors for any $d$ reduces to isomorphism of 3-tensors.

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Ok, I think you mean the number-of-provers hierachy: $\mbox{MIP}(2,1) = \mbox{MIP}$, $\mbox{MIP}^*(2,1) = \mbox{MIP}^*$. As far as I understand, in both cases, the "collapse" was done by showing that already a finite level reaches some obvious upper limit which in neither case was obviously reached by even the union of the hierarchy, and both were important results. $\endgroup$ – Ville Salo Aug 5 at 4:47
  • $\begingroup$ Or was it known that the hierarchies collapse even before the upper limit was known? The QMA class from another answer seems similar to these in spirit, and there $\mbox{QMA}(2) = \mbox{QMA}(k)$ is proved by direct simulation. $\endgroup$ – Ville Salo Aug 5 at 4:56
  • $\begingroup$ Ok, at least $\mbox{MIP}(2) = \mbox{MIP}$ was known before the collapse with $\mbox{NEXP}$, it's in the original paper groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf . $\endgroup$ – Ville Salo Aug 5 at 5:00
  • $\begingroup$ Hi @VilleSalo, thanks for your comments. Did you read the paper I posted? $\endgroup$ – Peter Morgan Aug 6 at 12:09
  • 1
    $\begingroup$ I skimmed it (after your answer, and also when the paper appeared), but I did not especially look for answers to my questions. Apologies if they are stated in plain English in the abstract... (It is not my area, most of the technical stuff goes over my head.) $\endgroup$ – Ville Salo Aug 6 at 12:14
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.