<p>As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as Savitch's <span class="math-container">$\textrm{NTIME}[S]\subset\textrm{DTIME}[S^2]$</span> and the famous PPST result that <span class="math-container">$\textrm{DTIME}[T]\neq\textrm{NTIME}[T]$</span>?</p>

<p>Is there any new research that I am unaware of with the goal of developing a deeper theory of complexity that could one day solve problems <span class="math-container">$P$</span> vs <span class="math-container">$NP$</span>, just as the theory of modular forms was developed to solve problems like Fermat's last theorem in number theory? And if not is it simply that we have run out of ideas to prove theorems like this, or have we turned to other measures of complexity for different reasons?</p>

CC BY-SA 4.0
2020-03-17T16:54:25.677Z
I'm unqualified to write a full answer, but as much work in classical complexity theory was motivated by solving $P\neq NP$, so looking into Scott Aaronson's [survey on that problem](https://www.scottaaronson.com/papers/pnp.pdf) may be useful. One might say that Geometric Complexity Theory is precisely the area you're looking for, but I'm unsure if it has developed any new complexity-theoretic results yet (instead of providing an alternative perspective on past results).
Note that the issue isn't simply we've "run out of ideas", but that we can prove many of our common tricks don't work.
Mark Schultz-Wu
CC BY-SA 4.0
2020-03-17T17:08:40.177Z
@Mark Thank you for the comment! I had read Scott Aaronson's survey before and forgot about it when writing this question, so this was a good reminder. The only sections that seem to be relatively recent are the results of Ryan Williams and the geometric complexity theory approach you mentioned. I wonder if these are the only approaches that the community still has hope for. I would hope not as the current results in geometric complexity theory are rather pessimistic, and Ryan Williams' approach can only go so far.
exfret
CC BY-SA 4.0
2020-03-17T17:11:46.687Z
@Mark Also, I would argue that being able to come up with methods that we know don't work isn't mutually exclusive with "running out of ideas" :)
exfret
CC BY-SA 4.0
2020-03-17T18:26:59.737Z
I'll just quickly mention that this area is typically known as "Structural Complexity theory". $P\neq\mathsf{NP}$ is clearly a large open question, but so is $\mathsf{VP}\neq\mathsf{VNP}$ (often referred to as the "permanent vs determinant" problem), which geometric complexity theory tries to attack. There are other unrelated questions though, such as $\mathsf{P} = \mathsf{BPP}$ (relevant authors are Wigderson and Impagliazzo), which is generally summarized as the "Hardness vs Pseudorandomness" research program. There are additional questions in circuit complexity, but the ones I know are...
Mark Schultz-Wu
CC BY-SA 4.0
2020-03-17T18:34:36.340Z
... simply stepping stones to proving $P\neq NP$ (and covered in the aforementioned survey). I know other students in my office have been working on things like extensions to the Easy Witness Lemma, or trying to get improved/generalized Karp Lipton lemmas, which I'm unclear if constitute answers to your question --- on one hand, they're current research in structural complexity theory. On the other hand, I do not know if the research is done with the goal of being a stepping stone to $P\neq NP$ (whereas this is the motivation for GCT).
Mark Schultz-Wu
CC BY-SA 4.0
2020-03-17T18:37:37.410Z
I suppose "structural complexity theory" is a more accurate term. I'll look into the topics you mention. Thank you!
exfret
CC BY-SA 4.0
2020-03-17T23:16:09.003Z
Have you looked at the list of recent preprints on [ECCC](https://eccc.weizmann.ac.il/)? And the less recent ones? You have results on VP v. VNP, arithmetic circuits lower bounds, NP-Hardness of Circuit Minimization, circuit lower bounds... all the above in the past couple months. (If you go earlier, you'll get more.)
Clement C.
CC BY-SA 4.0
2020-03-18T01:54:32.347Z
I was looking at arxiv, which did not have many helpful results. I actually was not aware of ECCC (which is a little embarrassing), so this was really helpful. I’m a little concerned of the focus on circuits, but at least some research is being done.
exfret
<cc.complexity-theory><soft-question>
What research is being done in classical complexity theory?
exfret
# What research is being done in classical complexity theory?

(Asked by: username_0 on 2020-03-17)

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as Savitch's $\textrm{NTIME}[S]\subset\textrm{DTIME}[S^2]$ and the famous PPST result that $\textrm{DTIME}[T]\neq\textrm{NTIME}[T]$?

Is there any new research that I am unaware of with the goal of developing a deeper theory of complexity that could one day solve problems $P$ vs $NP$, just as the theory of modular forms was developed to solve problems like Fermat's last theorem in number theory? And if not is it simply that we have run out of ideas to prove theorems like this, or have we turned to other measures of complexity for different reasons?

**Tags:** cc.complexity-theory, soft-question
> **Comments:**
> **username_1**: I'm unqualified to write a full answer, but as much work in classical complexity theory was motivated by solving $P\neq NP$, so looking into Scott Aaronson's [survey on that problem](https://www.scottaaronson.com/papers/pnp.pdf) may be useful. One might say that Geometric Complexity Theory is precisely the area you're looking for, but I'm unsure if it has developed any new complexity-theoretic results yet (instead of providing an alternative perspective on past results). Note that the issue isn't simply we've "run out of ideas", but that we can prove many of our common tricks don't work.  
> **username_0**: @Mark Thank you for the comment! I had read Scott Aaronson's survey before and forgot about it when writing this question, so this was a good reminder. The only sections that seem to be relatively recent are the results of Ryan Williams and the geometric complexity theory approach you mentioned. I wonder if these are the only approaches that the community still has hope for. I would hope not as the current results in geometric complexity theory are rather pessimistic, and Ryan Williams' approach can only go so far.  
> **username_0**: @Mark Also, I would argue that being able to come up with methods that we know don't work isn't mutually exclusive with "running out of ideas" :)  
> **username_1**: I'll just quickly mention that this area is typically known as "Structural Complexity theory". $P\neq\mathsf{NP}$ is clearly a large open question, but so is $\mathsf{VP}\neq\mathsf{VNP}$ (often referred to as the "permanent vs determinant" problem), which geometric complexity theory tries to attack. There are other unrelated questions though, such as $\mathsf{P} = \mathsf{BPP}$ (relevant authors are Wigderson and Impagliazzo), which is generally summarized as the "Hardness vs Pseudorandomness" research program. There are additional questions in circuit complexity, but the ones I know are...  
> **username_1**: ... simply stepping stones to proving $P\neq NP$ (and covered in the aforementioned survey). I know other students in my office have been working on things like extensions to the Easy Witness Lemma, or trying to get improved/generalized Karp Lipton lemmas, which I'm unclear if constitute answers to your question --- on one hand, they're current research in structural complexity theory. On the other hand, I do not know if the research is done with the goal of being a stepping stone to $P\neq NP$ (whereas this is the motivation for GCT).  
> **username_0**: I suppose "structural complexity theory" is a more accurate term. I'll look into the topics you mention. Thank you!  
> **username_2**: Have you looked at the list of recent preprints on [ECCC](https://eccc.weizmann.ac.il/)? And the less recent ones? You have results on VP v. VNP, arithmetic circuits lower bounds, NP-Hardness of Circuit Minimization, circuit lower bounds... all the above in the past couple months. (If you go earlier, you'll get more.)  
> **username_0**: I was looking at arxiv, which did not have many helpful results. I actually was not aware of ECCC (which is a little embarrassing), so this was really helpful. I’m a little concerned of the focus on circuits, but at least some research is being done.  

---

## 0 answers

