18 votes

Examples of collapsing hierarchies

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

Is $UL\neq PSPACE$ known?

$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so ...
  • 1,743
10 votes

Examples of collapsing hierarchies

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

$DTIME_1(o(n^2))\setminus$ REGULAR

For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you ...
9 votes
Accepted

Is Church-pentation implementable in Agda?

According to the paper you linked, I think the answer to the question you want to ask is, "no." Pentation is not definable in a stratified version of system F. The paper says that their system can ...
  • 650
8 votes

Examples of collapsing hierarchies

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".
  • 81
8 votes

Examples of collapsing hierarchies

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 ...
  • 1,101
7 votes
Accepted

Does the space hierarchy theorem generalize to non-uniform computation?

One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching ...
  • 1,743
7 votes

Examples of collapsing hierarchies

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\...
5 votes

Examples of collapsing hierarchies

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}\...
5 votes

Examples of collapsing hierarchies

k-SAT collapses at 3, of course.
5 votes

Examples of collapsing hierarchies

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]$ ...
  • 7,757
5 votes

Examples of collapsing hierarchies

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 ...
5 votes
Accepted

Is there a 'very fast growing' hierarchy that would capture System F?

Typically, fast growing hierarchies are characterized by ordinal notations, which are really just ways to express fast-growing functions (but it's sometimes convenient to see them as ordinals in the ...
  • 13.3k
4 votes

Examples of collapsing hierarchies

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 ...
4 votes

Examples of collapsing hierarchies

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 ...
3 votes

Examples of collapsing hierarchies

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,...
  • 376
3 votes

Examples of collapsing hierarchies

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 ...
3 votes

What hierarchies and/or hierarchy theorems do you know?

From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the ...
3 votes

What hierarchies and/or hierarchy theorems do you know?

Elaborating on one of the bullet points mentioned by the OP (GoldreichKNR09): there are several hierarchy theorems in property testing and proofs of proximity, relating to the query complexity, the ...
2 votes

Examples of collapsing hierarchies

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

What hierarchies and/or hierarchy theorems do you know?

Lasserre Hierarchy: An Hierarchy of progressively stronger (i.e., tighter, in the sense of integrality gaps) SDP relaxations of fractional polytopes J. Lasserre. An explicit exact SDP relaxation for ...
1 vote

What hierarchies and/or hierarchy theorems do you know?

Consider the Unambiguous Polynomial Hierarchy, reference here, original reference here for the unambiguous polynomial hierarchy(paywalled). While studying the Boolean hierarchy BH, and classes such ...
1 vote

What hierarchies and/or hierarchy theorems do you know?

The Polynomial Hierarchy in communication complexity as defined by Babai, Frankl, and Simon (see the original paper here and without the paywall here). The significance of this hierarchy is hard to ...

Only top scored, non community-wiki answers of a minimum length are eligible