<p>The analogue of the <span class="math-container">$\mathsf{NC}$</span> hierarchy for algebraic circuits is known to collapse to the second level. That is, algebraic circuits of size <span class="math-container">$n^{O(1)}$</span> computing a polynomial of degree <span class="math-container">$n^{O(1)}$</span> can be rebalanced to have depth <span class="math-container">$O(\log^2 n)$</span> while only increasing the size by a polynomial factor. This is due to Valiant, Skyum, Berkowitz, and Rackoff. It is open whether <span class="math-container">$\mathsf{NC}^1 \stackrel{?}{=} \mathsf{NC}^2$</span> in this setting, but I believe the popular opinion is that <span class="math-container">$\mathsf{NC}^1 \neq \mathsf{NC}^2$</span> here.</p>
<p>If one further restricts to <em>syntactically multilinear</em> algebraic circuits, then we in fact know <span class="math-container">$\mathsf{NC}^0 \subsetneq \mathsf{NC}^1 \subsetneq \mathsf{NC}^2 = \mathsf{NC}$</span> unconditionally. The fact that <span class="math-container">$\mathsf{NC}^1 \subsetneq \mathsf{NC}^2$</span> is due to Raz, and the fact that <span class="math-container">$\mathsf{NC}^2 = \mathsf{NC}$</span> is due to Raz and Yehudayoff.</p>
<p><em>Raz, Ran</em>, <a href="http://dx.doi.org/10.4086/toc.2006.v002a006" rel="noreferrer"><strong>Separation of multilinear circuit and formula size</strong></a>, Theory Comput. 2, Paper No. 6, 121-135 (2006). <a href="https://zbmath.org/?q=an:1213.68301" rel="noreferrer">ZBL1213.68301</a>.</p>
<p><em>Raz, Ran; Yehudayoff, Amir</em>, <a href="http://dx.doi.org/10.1007/s00037-008-0254-0" rel="noreferrer"><strong>Balancing syntactically multilinear arithmetic circuits</strong></a>, Comput. Complexity 17, No. 4, 515-535 (2008). <a href="https://zbmath.org/?q=an:1188.68367" rel="noreferrer">ZBL1188.68367</a>.</p>
<p><em>Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C.</em>, <a href="http://dx.doi.org/10.1137/0212043" rel="noreferrer"><strong>Fast parallel computation of polynomials using few processors</strong></a>, SIAM J. Comput. 12, 641-644 (1983). <a href="https://zbmath.org/?q=an:0524.68028" rel="noreferrer">ZBL0524.68028</a>.</p>

CC BY-SA 4.0
2020-08-04T16:34:27.920Z
Very cool, I had no idea!
Ville Salo
CC BY-SA 4.0
2020-08-04T15:23:24.803Z
2020-08-04T15:23:24.803Z
Robert Andrews
<p>The AM hierarchy (constant-round interactive proofs) collapses to AM (Babai-Moran '88), but we don't yet know whether NP=MA=AM.</p>

CC BY-SA 4.0
2020-08-05T05:10:12.287Z
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.)
Ville Salo
CC BY-SA 4.0
2020-08-07T17:30:24.640Z
@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.
Joshua Grochow
CC BY-SA 4.0
2020-08-08T06:33:43.853Z
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.
Ville Salo
CC BY-SA 4.0
2020-08-08T06:36:05.410Z
(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.)
Ville Salo
CC BY-SA 4.0
2020-08-04T21:54:21.003Z
2020-08-04T21:54:21.003Z
Joshua Grochow
<p>When I was in graduate school, I once presented for a class a paper from a STOC conference (mid-80's) entitled &quot;The Strong Exponential Hierarchy Collapses&quot;.</p>

CC BY-SA 4.0
2020-08-05T12:29:50.340Z
I guess this is the journal version: https://www.sciencedirect.com/science/article/pii/0022000089900251
Ville Salo
CC BY-SA 4.0
2020-08-05T12:25:08.160Z
2020-08-05T12:25:08.160Z
PMar
<p>Barrington’s theorem: if <span class="math-container">$\def\bp{\mathrm{BP}}\bp_k$</span> denotes the class of languages computable by polynomial-size width-<span class="math-container">$k$</span> branching programs, we have
<span class="math-container">$$\bp_1\subsetneq\bp_2\subsetneq\bp_3\subseteq\bp_4\subseteq\bp_5=\bigcup_{k\in\mathrm N}\bp_k=\mathrm{NC}^1.$$</span>
Note that <span class="math-container">$\bp_4\subseteq\mathrm{AC}^0[6]$</span>, hence likely <span class="math-container">$\bp_4\subsetneq\bp_5$</span>.</p>

CC BY-SA 4.0
2020-08-08T18:36:19.107Z
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$.
Nikhil
CC BY-SA 4.0
2020-08-08T08:21:46.450Z
2020-08-08T14:01:16.510Z
2020-08-08T14:01:16.510Z
Emil Jeřábek
<p>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 <a href="https://arxiv.org/abs/1001.0017" rel="nofollow noreferrer">Harrow, Montanaro</a> where QMA(2) =QMA(k) for k &gt;= 2.</p>
<p>More collapsing results:</p>
<p>The <span class="math-container">$PL$</span> (Probabilistic Logspace) hierarchy collapses, ie  <span class="math-container">$ PLH$</span> = <span class="math-container">$PL$</span>. See <a href="https://www.academia.edu/33000392/The_PL_hierarchy_collapses" rel="nofollow noreferrer"> paper here. </a>.  The relativization model used is the Russo-Simon-Tompa relativization model. The choice of relativization is noted in the definition of the hierarchy.</p>
<p>Another collapse result related to the counting classes, and &quot;exact&quot; Arithmetic Hierarchies, <a href="https://eccc.weizmann.ac.il/report/2013/131/" rel="nofollow noreferrer"> reference here</a>.  The collapse is to the third level of the <span class="math-container">$AC^{0}$</span> -hierarchy.</p>

CC BY-SA 4.0
2020-08-05T05:13:51.923Z
Ok, collapse in number of Merlins in a quantum Merlin-Arthur protocol. Two Merlins suffice.
Ville Salo
CC BY-SA 4.0
2020-08-08T23:34:43.660Z
The original paper on which the exact Arithmetic Hierarchies collapse paper is based is by Allender-Beals-Ogihara (https://www.cs.rutgers.edu/~allender/papers/rank.pdf). The PP hierarchy is shown to collapse by Beigel-Fu.
SamiD
CC BY-SA 4.0
2020-08-04T18:07:52.763Z
2020-08-08T08:00:19.483Z
2020-08-08T08:00:19.483Z
user3483902
<p>k-SAT collapses at 3, of course.</p>

CC BY-SA 4.0
2020-08-05T12:02:47.077Z
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.
Ville Salo
CC BY-SA 4.0
2020-08-05T11:39:58.163Z
2020-08-05T11:39:58.163Z
Ralph Furman
<p>From computability theory we have the <strong>Ershov hierarchy</strong>, or rather its &quot;naive linearization.&quot;</p>
<p>The goal of the Ershov hierarchy is to analyze the <span class="math-container">$\Delta^0_2$</span> sets - that is, the sets computable from the halting problem <a href="https://en.wikipedia.org/wiki/Turing_jump" rel="noreferrer"><span class="math-container">$\emptyset'$</span></a>. The starting point is to generalize the c.e. sets:</p>
<ul>
<li><p>A set is <span class="math-container">$1$</span>-c.e. iff it is c.e., and a set is co-<span class="math-container">$1$</span>-c.e. if it is co-c.e.</p>
</li>
<li><p>A set is <span class="math-container">$(n+1)$</span>-c.e. iff it is of the form <span class="math-container">$A\setminus B$</span> for <span class="math-container">$A$</span> <span class="math-container">$n$</span>-c.e. and <span class="math-container">$B$</span> c.e., and a set is co-<span class="math-container">$(n+1)$</span>-c.e. if its complement is <span class="math-container">$(n+1)$</span>-c.e.</p>
</li>
</ul>
<p>This is all nice and simple, but it doesn't finish the job: there are <span class="math-container">$\Delta^0_2$</span> sets which are not Turing equivalent to any <span class="math-container">$n$</span>-c.e. set for any <span class="math-container">$n\in\mathbb{N}$</span>. To get all the <span class="math-container">$\Delta^0_2$</span> sets we need to go into the transfinite. The basic idea is that a set <span class="math-container">$A$</span> is at the <span class="math-container">$l$</span>th level of the hierarchy for <span class="math-container">$l$</span> a computable well-ordering if there is a computable &quot;approximation&quot; function <span class="math-container">$f(x,s)$</span> and a computable &quot;clock&quot; function <span class="math-container">$g(x,s)$</span> such that:</p>
<ul>
<li><p><span class="math-container">$\lim_{s\rightarrow\infty} f(x,s)=A(x)$</span> (so <span class="math-container">$f$</span> yields a <span class="math-container">$\Delta^0_2$</span> description of <span class="math-container">$A$</span>), and</p>
</li>
<li><p><span class="math-container">$g:\mathbb{N}^2\rightarrow l$</span> is nonincreaning and satisfies <span class="math-container">$$f(x,s)\not=f(x,s+1)\implies g(x,s)&gt;_l g(x,s+1).$$</span></p>
</li>
</ul>
<p>Since <span class="math-container">$l$</span> is well-ordered, the clock <span class="math-container">$g$</span> eventually stops &quot;ticking&quot; and so our approximator <span class="math-container">$f$</span> can only change its mind finitely many times. So all of these sets are limit computable, hence <span class="math-container">$\le_T \emptyset'$</span>.</p>
<p><em>For the precise definition of the Ershov hierarchy see <a href="https://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=&amp;ved=2ahUKEwjs8bbd74TrAhUMK80KHX8IDzQQFjADegQIBhAB&amp;url=https%3A%2F%2Fwww.comp.nus.edu.sg%2F%7Efstephan%2Fsyy.ps&amp;usg=AOvVaw1x8ozx8ZgDZ4IrYM0Vup7_" rel="noreferrer">here</a></em></p>
<p>The problem - as often happens with such ideas - is that in the definitions of <span class="math-container">$l$</span>-c.e.ness and co-<span class="math-container">$l$</span>-c.e.ness the object <span class="math-container">$l$</span> is not an ordinal but rather a <em>specific presentation</em> of an ordinal: we can have two computable well-orderings <span class="math-container">$l_0,l_1$</span> of the same ordertype such that there is an <span class="math-container">$l_0$</span>-c.e. set which is not <span class="math-container">$l_1$</span>-c.e. So really, the Ershov &quot;hierarchy&quot; isn't a linear hierarchy at all: rather than being indexed by ordinals <span class="math-container">$&lt;\omega_1^{CK}$</span> it's indexed by <a href="https://en.wikipedia.org/wiki/Kleene%27s_O" rel="noreferrer">ordinal notations</a>.</p>
<p>A natural hope at this point is that we can &quot;linearize&quot; things: for <span class="math-container">$\alpha$</span> an ordinal <span class="math-container">$&lt;\omega_1^{CK}$</span>, say that <span class="math-container">$A$</span> is <strong>optimally <span class="math-container">$\alpha$</span>-c.e.</strong> iff <span class="math-container">$A$</span> is <span class="math-container">$l$</span>-c.e. for some computable well-ordering <span class="math-container">$l$</span> of ordertype <span class="math-container">$\alpha$</span>. This trivially gets us a genuine linear hierarchy, since the ordinals themselves are linearly ordered. However, this new hierarchy collapses: every <span class="math-container">$\Delta^0_2$</span> set is <span class="math-container">$l$</span>-c.e. for some presentation <span class="math-container">$l$</span> of <span class="math-container">$\omega^2$</span>, so the &quot;optimal Ershov hierarchy&quot; collapses at level <span class="math-container">$\omega^2$</span>.</p>
<hr />
<p>What makes this particularly interesting is its contrast with a seemingly-similar construction: the <strong>hyperarithmetic hierarchy</strong>. Here again we have a &quot;hierarchy&quot; indexed by ordinal notations: for a well-ordering <span class="math-container">$l$</span> of <span class="math-container">$\mathbb{N}$</span> (computable or not!) there is a natural way to iterate the Turing jump along <span class="math-container">$l$</span>, and the hyperarithmetic sets are those computable from some iterate of the jump along a computable well-ordering starting with <span class="math-container">$\emptyset$</span>. So this superficially has the same flavor as the Ershov hierarchy.</p>
<p>But now we have a very surprising, in light of the above, well-definedness phenomenon: if <span class="math-container">$l_0,l_1$</span> are computable well-orderings of <span class="math-container">$\mathbb{N}$</span> with the same ordertype <span class="math-container">$\alpha&lt;\omega_1^{CK}$</span>, then <span class="math-container">$X^{(l_0)}\equiv_TX^{(l_1)}$</span> for every set <span class="math-container">$X$</span>. Consequently we get an increasing sequence of Turing degrees of length <span class="math-container">$\omega_1^{CK}$</span>, such that the hyperarithmetic sets are exactly the sets computable from some member of this sequence.</p>
<p><a href="https://projecteuclid.org/euclid.pl/1235422634" rel="noreferrer">Sacks' book</a> gives a good treatment of this topic.</p>

CC BY-SA 4.0
2020-08-06T05:24:31.230Z
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*.
Ville Salo
CC BY-SA 4.0
2020-08-06T05:25:55.197Z
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?
Ville Salo
CC BY-SA 4.0
2020-08-05T20:15:30.487Z
2020-08-05T20:15:30.487Z
Noah Schweber
<p>The parity acceptance condition for automata on infinite words induces a hierarchy of type <span class="math-container">$\Sigma_i/\Pi_i$</span>, noted <span class="math-container">$[0,i]$</span> and <span class="math-container">$[1,i+1]$</span> with <span class="math-container">$i\in\mathbb N$</span>.
The parity condition of level <span class="math-container">$[a,b]$</span> works as follows: each state is labelled with an integer in <span class="math-container">$[a,b]$</span>, and an infinite run is accepting iff the largest integer appearing infinitely often is even.</p>
<p>For nondeterministic automata, the hierarchy collapses at the level <span class="math-container">$[1,2]$</span>, meaning that every regular language of infinite words can be accepted by a nondeterministic <span class="math-container">$[1,2]$</span>-automaton, also known as Büchi automata.</p>
<p>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.</p>

CC BY-SA 4.0
2020-08-05T21:49:26.153Z
2020-08-07T18:24:43.223Z
2020-08-07T18:24:43.223Z
Denis
<p>Recall that for any prime <span class="math-container">$p$</span>, the modulo-<span class="math-container">$p$</span> counting hierarchy <span class="math-container">$\def\modph#1{\mathrm{Mod}_{#1}\mathrm{PH}}\modph p$</span> is defined as the smallest class of languages such that</p>
<ul>
<li><span class="math-container">$\mathrm{NP}^{\modph p}\let\sset\subseteq\sset\modph p$</span>,</li>
<li><span class="math-container">$\oplus_p\mathrm P^{\modph p}\sset\modph p$</span>.</li>
</ul>
<p>Toda’s theorem ensures that it collapses to
<span class="math-container">$$\modph p=\mathrm{BP}\cdot\oplus_p\mathrm P=\exists\forall\cdot\oplus_p\mathrm P=\forall\exists\cdot\oplus_p\mathrm P.$$</span>
Depending on how exactly you count it, this is around the second or third level of the hierarchy.</p>

CC BY-SA 4.0
2020-08-08T08:31:02.597Z
2020-08-08T10:56:35.623Z
2020-08-08T10:56:35.623Z
Emil Jeřábek
<p>Isomorphism of <span class="math-container">$d$</span>-tensors for any <span class="math-container">$d$</span> reduces to isomorphism of 3-tensors. (<a href="https://doi.org/10.4230/LIPIcs.ITCS.2021.31" rel="nofollow noreferrer">G.-Qiao, ITCS '21</a>).</p>
<p>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 <span class="math-container">$q^{O(n^2)}$</span> algorithm for <span class="math-container">$n \times n \times n$</span> tensors over <span class="math-container">$\mathbb{F}_q$</span>). This seems strictly harder than isomorphism of 2-tensors=matrices, which is in <span class="math-container">$\mathsf{NC}^2$</span>, and which in turn seems strictly harder than isomorphism of 1-tensors=vectors, which is completely trivial, as any two nonzero vectors are &quot;isomorphic.&quot;</p>
<p>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 <span class="math-container">$\mathsf{NP}$</span>-complete unless <span class="math-container">$\mathsf{PH}$</span> collapses, so one cannot use any such trick. The reduction for tensors is pretty involved.</p>

CC BY-SA 4.0
2020-08-06T00:17:22.293Z
2021-02-21T04:58:18.360Z
2021-02-21T04:58:18.360Z
Joshua Grochow
<p>With three counters (or any larger amount) you can recognize precisely the recursively enumerable sets <span class="math-container">$A \subset \mathbb{N}$</span>. With two counters, you cannot recognize the prime numbers or <span class="math-container">$e$</span>th powers of natural numbers for fixed <span class="math-container">$e \geq 2$</span>.</p>
<p>Two heads are already quite powerful: the sets <span class="math-container">$\{2^n \;|\; n \in A\}$</span> you can accept are precisely the ones where <span class="math-container">$A$</span> is recursively enumerable.</p>
<p>One head is of little interest (accepts exactly the semilinear sets).</p>
<p>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.</p>
<p><em>Ibarra, Oscar H.; Trân, Nicholas Q.</em>, <a href="http://dx.doi.org/10.1016/0304-3975(93)90028-R" rel="nofollow noreferrer"><strong>A note on simple programs with two variables</strong></a>, Theor. Comput. Sci. 112, No. 2, 391-397 (1993). <a href="https://zbmath.org/?q=an:0785.68033" rel="nofollow noreferrer">ZBL0785.68033</a>.</p>

CC BY-SA 4.0
2020-08-05T11:58:10.163Z
2020-08-05T12:04:14.793Z
2020-08-05T12:04:14.793Z
Ville Salo
<p>The bounded (relational) width hierarchy of constraint satisfaction problem templates collapses: this was proved in <em>Barto, Libor</em>, <a href="http://dx.doi.org/10.1093/logcom/exu070" rel="nofollow noreferrer"><strong>The collapse of the bounded width hierarchy</strong></a>, J. Log. Comput. 26, No. 3, 923-943 (2016). <a href="https://zbmath.org/?q=an:1353.68107" rel="nofollow noreferrer">ZBL1353.68107</a>. The same result was also proved independently by Andrei Bulatov in an unpublished manuscript (<a href="https://www2.cs.sfu.ca/%7Eabulatov/papers/relwidth.pdf" rel="nofollow noreferrer">link</a>) around the same time.</p>
<p>The collapse was then sharpened in <em>Kozik, Marcin</em>, <a href="http://dx.doi.org/10.1145/2933575.2934510" rel="nofollow noreferrer"><strong>Weak consistency notions for all the CSPs of bounded width</strong></a>, 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). <a href="https://zbmath.org/?q=an:1401.68123" rel="nofollow noreferrer">ZBL1401.68123</a>. This was later sharpened further in <a href="https://marcinkozik.staff.tcs.uj.edu.pl/Solving.CSPs.using.weak.local.consistency.pdf" rel="nofollow noreferrer">this paper</a>, also by Kozik.</p>
<p>A constraint satisfaction problem template is a finite domain <span class="math-container">$D$</span> of values that variables may take (such as <span class="math-container">$\{r,g,b\}$</span> for the <span class="math-container">$3$</span>-coloring problem), together with a finite set of relations <span class="math-container">$\Gamma = \{R_1, R_2, ...\}$</span>, with each <span class="math-container">$R_i$</span> a <span class="math-container">$k_i$</span>-ary relation which may be described explicitly as a subset of <span class="math-container">$D^{k_i}$</span>, that may be used to build puzzles (for the <span class="math-container">$3$</span>-coloring problem, we would take <span class="math-container">$\Gamma = \{\ne\}$</span>, where <span class="math-container">$\ne$</span> is the binary relation on <span class="math-container">$\{r,g,b\}$</span> corresponding to the set <span class="math-container">$\{r,g,b\}^2 \setminus \{(r,r),(g,g),(b,b)\}$</span>). Specific puzzles built using relations from <span class="math-container">$\Gamma$</span> are known as &quot;instances&quot; of the CSP template <span class="math-container">$(D,\Gamma)$</span>.</p>
<p>For a given CSP template <span class="math-container">$(D,\Gamma)$</span>, it is natural to ask whether certain simple &quot;local propagation&quot; algorithms can decide every instance of <span class="math-container">$(D,\Gamma)$</span>. The simplest &quot;local propagation&quot; algorithm is called arc consistency (or generalized arc consistency/hyper-arc consistency, if the relations have arity greater than <span class="math-container">$2$</span>) - this strategy is the strategy most beginner Sudoku players use. Slightly more complex local propagation strategies are described in <a href="https://en.wikipedia.org/wiki/Local_consistency" rel="nofollow noreferrer">this wikipedia page</a>.</p>
<p>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 <span class="math-container">$k$</span> variables at a time (or, if <span class="math-container">$k$</span> is less than the maximum arity <span class="math-container">$k_i$</span> of any relation <span class="math-container">$R_i$</span> in <span class="math-container">$\Gamma$</span>, 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).</p>
<p>The full bounded width hierarchy then collapses to the following few layers (each strictly contained in the next):</p>
<ul>
<li>the templates that can be solved by (generalized) arc consistency (one such template is HORN-SAT),</li>
<li>the templates that can be solved by the basic linear programming relaxation,</li>
<li>the templates that can be solved by &quot;cycle consistency&quot;: 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 <span class="math-container">$3$</span>rd level of the Datalog hierarchy described above.</li>
</ul>
<p>Anything which is not in one of those layers can simulate systems of affine-linear equations modulo a prime <span class="math-container">$p$</span>, and thus can't be solved at any level of the bounded width hierarchy.</p>
<p>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 <em>Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar</em>, <a href="http://dx.doi.org/10.1137/1.9781611973730.58" rel="nofollow noreferrer"><strong>Towards a characterization of constant-factor approximable min CSPs</strong></a>, 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). <a href="https://zbmath.org/?q=an:1371.90116" rel="nofollow noreferrer">ZBL1371.90116</a>.</p>

CC BY-SA 4.0
2020-08-11T08:45:36.460Z
2020-08-11T08:45:36.460Z
zeb
<p>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:</p>
<p>The alternating logspace hierarchy <span class="math-container">$\Sigma_k^{\log}=\Sigma_k\text-\mathrm{SPACE}(\log n)$</span> collapses to <span class="math-container">$\mathrm{NL=coNL}$</span> by the Immerman–Szelepcsényi theorem. (It is a lesser known fact that shortly before that, it was shown to collapse to <span class="math-container">$\Sigma^{\log}_2=\Pi^{\log}_2$</span> by <a href="https://doi.org/10.1016/0890-5401(89)90012-6" rel="nofollow noreferrer">Jenner, Kirsig &amp; Lange</a>.)</p>

CC BY-SA 4.0
2020-08-08T08:50:12.000Z
2020-08-08T08:50:12.000Z
Emil Jeřábek
<p>Perhaps this recent result (Jan 2020) showing that <a href="https://arxiv.org/abs/2001.04383" rel="nofollow noreferrer">MIP* = RE</a>.</p>

CC BY-SA 4.0
2020-08-05T04:47:37.000Z
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.
Ville Salo
CC BY-SA 4.0
2020-08-05T04:56:32.123Z
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.
Ville Salo
CC BY-SA 4.0
2020-08-05T05:00:52.910Z
Ok, at least $\mbox{MIP}(2) = \mbox{MIP}$ was known before the collapse with $\mbox{NEXP}$, it's in the original paper http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf .
Ville Salo
CC BY-SA 4.0
2020-08-06T12:09:36.477Z
Hi @VilleSalo, thanks for your comments. Did you read the paper I posted?
Peter Morgan
CC BY-SA 4.0
2020-08-06T12:14:37.753Z
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.)
Ville Salo
CC BY-SA 4.0
2020-08-04T18:38:20.137Z
2020-08-04T18:38:20.137Z
Peter Morgan
<blockquote>
<p>Are there interesting examples of &quot;collapsing hierarchies&quot; in computer science?</p>
</blockquote>
<p>The formal definition of a <em>hierarchy</em> 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 &quot;natural&quot; hierachy, where the parameter represents some type of resource. I am particularly interested in hierarchies where the parameter space is <span class="math-container">$\mathbb{N}$</span> or the <span class="math-container">$\Sigma_i/\Pi_i$</span> ladder. Some examples are</p>
<ul>
<li>the polynomial hierarchy (counting alternations),</li>
<li>the lightface hierarchy (same),</li>
<li><span class="math-container">$NC^i$</span> and <span class="math-container">$AC^i$</span>,</li>
<li>various ways to associate languages to <span class="math-container">$k$</span>-headed finite-state automata (as <span class="math-container">$k$</span> grows).</li>
</ul>
<p>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.</p>
<p>By <em>collapsing</em> 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 &quot;natural&quot;, and I would prefer an example where the collapse does not happen &quot;on the first level&quot;.</p>
<p>I did not carefully check that none of the hierarchies listed in <a href="https://cstheory.stackexchange.com/questions/7303/what-hierarchies-and-or-hierarchy-theorems-do-you-know">What hierarchies and/or hierarchy theorems do you know?</a> 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.</p>

CC BY-SA 4.0
2020-08-04T13:47:58.497Z
I am assuming this is a relatively rare phenomenon, so don't be shy if you know a really obscure example.
Ville Salo
CC BY-SA 4.0
2020-08-04T14:26:46.537Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-08-04T14:31:15.527Z
Concerning your last paragraph, this is to be expected, as once a hierarchy is known to collapse, it generally stops being called a hierarchy.
Emil Jeřábek
CC BY-SA 4.0
2020-08-04T14:52:55.457Z
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?
Ville Salo
CC BY-SA 4.0
2020-08-04T14:54:51.917Z
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.
Ville Salo
CC BY-SA 4.0
2020-08-08T08:51:24.457Z
Ok, I converted the comment to answers.
Emil Jeřábek
<big-list><hierarchy-theorems>
Examples of collapsing hierarchies
Ville Salo
# Examples of collapsing hierarchies

(Asked by: username_0 on 2020-08-04)

> 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?](https://cstheory.stackexchange.com/questions/7303/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.

**Tags:** big-list, hierarchy-theorems
> **Comments:**
> **username_0**: I am assuming this is a relatively rare phenomenon, so don't be shy if you know a really obscure example.  
> **username_1**: 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.  
> **username_1**: Concerning your last paragraph, this is to be expected, as once a hierarchy is known to collapse, it generally stops being called a hierarchy.  
> **username_0**: 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?  
> **username_0**: 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.  
> **username_1**: Ok, I converted the comment to answers.  

---

## 14 answers

### Answer by username_2 on 2020-08-04. Score: 18

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**](http://dx.doi.org/10.4086/toc.2006.v002a006), Theory Comput. 2, Paper No. 6, 121-135 (2006). [ZBL1213.68301](https://zbmath.org/?q=an:1213.68301).

*Raz, Ran; Yehudayoff, Amir*, [**Balancing syntactically multilinear arithmetic circuits**](http://dx.doi.org/10.1007/s00037-008-0254-0), Comput. Complexity 17, No. 4, 515-535 (2008). [ZBL1188.68367](https://zbmath.org/?q=an:1188.68367).

*Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C.*, [**Fast parallel computation of polynomials using few processors**](http://dx.doi.org/10.1137/0212043), SIAM J. Comput. 12, 641-644 (1983). [ZBL0524.68028](https://zbmath.org/?q=an:0524.68028).

> **Comments:**
> **username_0**: Very cool, I had no idea!  

---

### Answer by username_3 on 2020-08-04. Score: 10

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

> **Comments:**
> **username_0**: 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.)  
> **username_3**: @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.  
> **username_0**: 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.  
> **username_0**: (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.)  

---

### Answer by username_4 on 2020-08-05. Score: 8

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

> **Comments:**
> **username_0**: I guess this is the journal version: https://www.sciencedirect.com/science/article/pii/0022000089900251  

---

### Answer by username_1 on 2020-08-08. Score: 8

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

> **Comments:**
> **username_5**: 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$.  

---

### Answer by username_6 on 2020-08-04. Score: 8

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](https://arxiv.org/abs/1001.0017) where QMA(2) =QMA(k) for k >= 2.

More collapsing results:

The $PL$ (Probabilistic Logspace) hierarchy collapses, ie $ PLH$ = $PL$. See  [paper here.](https://www.academia.edu/33000392/The_PL_hierarchy_collapses) . 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](https://eccc.weizmann.ac.il/report/2013/131/). The collapse is to the third level of the $AC^{0}$ -hierarchy.

> **Comments:**
> **username_0**: Ok, collapse in number of Merlins in a quantum Merlin-Arthur protocol. Two Merlins suffice.  
> **username_7**: The original paper on which the exact Arithmetic Hierarchies collapse paper is based is by Allender-Beals-Ogihara (https://www.cs.rutgers.edu/~allender/papers/rank.pdf). The PP hierarchy is shown to collapse by Beigel-Fu.  

---

### Answer by username_8 on 2020-08-05. Score: 6

k-SAT collapses at 3, of course.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_9 on 2020-08-05. Score: 5

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'$](https://en.wikipedia.org/wiki/Turing_jump). 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](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjs8bbd74TrAhUMK80KHX8IDzQQFjADegQIBhAB&url=https%3A%2F%2Fwww.comp.nus.edu.sg%2F%7Efstephan%2Fsyy.ps&usg=AOvVaw1x8ozx8ZgDZ4IrYM0Vup7_)*

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](https://en.wikipedia.org/wiki/Kleene%27s_O).

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](https://projecteuclid.org/euclid.pl/1235422634) gives a good treatment of this topic.

> **Comments:**
> **username_0**: 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*.  
> **username_0**: 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?  

---

### Answer by username_10 on 2020-08-05. Score: 5

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 by username_1 on 2020-08-08. Score: 5

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 by username_3 on 2020-08-06. Score: 4

Isomorphism of $d$-tensors for any $d$ reduces to isomorphism of 3-tensors. ([G.-Qiao, ITCS '21](https://doi.org/10.4230/LIPIcs.ITCS.2021.31)).

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 by username_0 on 2020-08-05. Score: 4

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**](http://dx.doi.org/10.1016/0304-3975(93)90028-R), Theor. Comput. Sci. 112, No. 2, 391-397 (1993). [ZBL0785.68033](https://zbmath.org/?q=an:0785.68033).


---

### Answer by username_11 on 2020-08-11. Score: 3

The bounded (relational) width hierarchy of constraint satisfaction problem templates collapses: this was proved in *Barto, Libor*, [**The collapse of the bounded width hierarchy**](http://dx.doi.org/10.1093/logcom/exu070), J. Log. Comput. 26, No. 3, 923-943 (2016). [ZBL1353.68107](https://zbmath.org/?q=an:1353.68107). The same result was also proved independently by Andrei Bulatov in an unpublished manuscript ([link](https://www2.cs.sfu.ca/%7Eabulatov/papers/relwidth.pdf)) around the same time.

The collapse was then sharpened in *Kozik, Marcin*, [**Weak consistency notions for all the CSPs of bounded width**](http://dx.doi.org/10.1145/2933575.2934510), 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](https://zbmath.org/?q=an:1401.68123). This was later sharpened further in [this paper](https://marcinkozik.staff.tcs.uj.edu.pl/Solving.CSPs.using.weak.local.consistency.pdf), 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](https://en.wikipedia.org/wiki/Local_consistency).

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**](http://dx.doi.org/10.1137/1.9781611973730.58), 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](https://zbmath.org/?q=an:1371.90116).


---

### Answer by username_1 on 2020-08-08. Score: 3

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](https://doi.org/10.1016/0890-5401(89)90012-6).)


---

### Answer by username_12 on 2020-08-04. Score: 2

Perhaps this recent result (Jan 2020) showing that [MIP\* = RE](https://arxiv.org/abs/2001.04383).

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: Ok, at least $\mbox{MIP}(2) = \mbox{MIP}$ was known before the collapse with $\mbox{NEXP}$, it's in the original paper http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf .  
> **username_12**: Hi @VilleSalo, thanks for your comments. Did you read the paper I posted?  
> **username_0**: 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.)  

---

