<p>When we are trying to figure out in which complexity class a problem lies, we usually try simultaneously to come up with the best algorithm for it, together with the best hardness reduction, until (ideally) they both match the same known complexity class.</p>

<p>Imagine we show that the problem is $A$-hard, and lies in $B$, and $B\subseteq A$ is known but $A=B$ is an open problem in complexity theory. Then it is very likely that we made an error, and we will focus on trying to find it. If there is no error, this is a proof of $A=B$.</p>

<p>I'm curious whether it actually happened, that advances in complexity theory were made this way ? I.e. were open problems on equality of classes solved by trying to find out the exact complexity of a particular problem ? It would be a nice example of serendipity (sort of) for computer scientists.</p>

<p>Notice that the "opposite" happened often: new complexity classes were created to describe the complexity of a particular problem, when it could not be matched to known classes, for instance Graph Isomorphism.</p>

CC BY-SA 3.0
2015-10-28T14:11:57.660Z
Salut Denis ! The equality between $\mathsf L$ (log-space) and $\mathsf{SL}$ (symmetric log-space) was proven by Reingold by showing that *Undirected ST-connectivity* is $\mathsf L$-complete. Also, [Immerman-Szelepcsényi Theorem](https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem) was essentially proven by showing that *ST-unconnectivity* is in $\mathsf{NL}$. And more generally, I guess that *all* results of equality between classes are of this form. The $A$-hard problem is simply not natural in some cases.
Bruno
CC BY-SA 3.0
2015-10-28T16:19:42.283Z
Thanks Bruno, though it is a bit cheating, since SL is one of these classes that I mention in the end, which is defined as the complexity of undirected ST-connectivity. So here you don't really have a choice if you want to equate it with another class (here L), apart from showing that undirected ST-connectivity is in L. I was thinking more of classes defined by time/space resources, that are equated via specific problems instead of constructions on general Turing machines such as the proof of Savitch theorem for instance.
Denis
CC BY-SA 3.0
2015-10-28T16:26:23.707Z
@Bruno The second part about Immerman–Szelepcsényi theorem is an example of what I'm looking for though, you can make it into an answer !
Denis
CC BY-SA 4.0
2023-01-26T06:26:59.333Z
I guess the proof of IP=PSPACE is another one. Really uses the arithmetizability of the PSPACE-complete problem TQBF. This is one of the beautiful things about complexity classes having complete problems in the first place!
Joshua Grochow
<cc.complexity-theory><complexity-classes><ho.history-overview>
Advances in complexity by studying particular problems
Denis
# Advances in complexity by studying particular problems

(Asked by: username_0 on 2015-10-28)

When we are trying to figure out in which complexity class a problem lies, we usually try simultaneously to come up with the best algorithm for it, together with the best hardness reduction, until (ideally) they both match the same known complexity class.

Imagine we show that the problem is $A$-hard, and lies in $B$, and $B\subseteq A$ is known but $A=B$ is an open problem in complexity theory. Then it is very likely that we made an error, and we will focus on trying to find it. If there is no error, this is a proof of $A=B$.

I'm curious whether it actually happened, that advances in complexity theory were made this way ? I.e. were open problems on equality of classes solved by trying to find out the exact complexity of a particular problem ? It would be a nice example of serendipity (sort of) for computer scientists.

Notice that the "opposite" happened often: new complexity classes were created to describe the complexity of a particular problem, when it could not be matched to known classes, for instance Graph Isomorphism.

**Tags:** cc.complexity-theory, complexity-classes, ho.history-overview

> **Comments:**
> **username_1**: Salut username_0 ! The equality between $\mathsf L$ (log-space) and $\mathsf{SL}$ (symmetric log-space) was proven by Reingold by showing that *Undirected ST-connectivity* is $\mathsf L$-complete. Also, [Immerman-Szelepcsényi Theorem](https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem) was essentially proven by showing that *ST-unconnectivity* is in $\mathsf{NL}$. And more generally, I guess that *all* results of equality between classes are of this form. The $A$-hard problem is simply not natural in some cases.  
> **username_0**: Thanks username_1, though it is a bit cheating, since SL is one of these classes that I mention in the end, which is defined as the complexity of undirected ST-connectivity. So here you don't really have a choice if you want to equate it with another class (here L), apart from showing that undirected ST-connectivity is in L. I was thinking more of classes defined by time/space resources, that are equated via specific problems instead of constructions on general Turing machines such as the proof of Savitch theorem for instance.  
> **username_0**: @username_1 The second part about Immerman–Szelepcsényi theorem is an example of what I'm looking for though, you can make it into an answer !  
> **username_2**: I guess the proof of IP=PSPACE is another one. Really uses the arithmetizability of the PSPACE-complete problem TQBF. This is one of the beautiful things about complexity classes having complete problems in the first place!  

---

## 0 answers

