Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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)}$ ...
Robert Andrews's user avatar
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 ...
William Hoza's user avatar
  • 1,743
10 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 ...
Dan Doel's user avatar
  • 1,021
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.
Joshua Grochow's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
user3483902's user avatar
  • 1,261
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".
PMar's user avatar
  • 81
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 ...
William Hoza's user avatar
  • 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\...
Emil Jeřábek's user avatar
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}\...
Emil Jeřábek's user avatar
5 votes

Examples of collapsing hierarchies

k-SAT collapses at 3, of course.
Ralph Furman's user avatar
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 ...
cody's user avatar
  • 13.9k
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]$ ...
Denis's user avatar
  • 8,883
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 ...
Noah Schweber's user avatar
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 ...
Ville Salo's user avatar
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 ...
Joshua Grochow's user avatar
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,...
zeb's user avatar
  • 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 ...
Emil Jeřábek's user avatar
3 votes

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

The language $L=\{0^n1^n : n\geq 0\}$ is non-regular, but decidable in time $O(n\log n)$ on a one-tape Turing machine (one can either use a counter or iteratively remove every next 0 and 1 plus check ...
QMath's user avatar
  • 303
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.
Peter Morgan's user avatar
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

Arithmetic Circuit Hierarchy?

This question has a somewhat trivial answer because the polynomial $x^{2^s}$ requires $s$ multiplications, so you can just take $h = x_1^{2^{f(n)}}$. This is one of the reasons why in algebraic ...
Vladimir Lysikov's user avatar
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 ...

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