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?

  • 4
    $\begingroup$ 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 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. $\endgroup$ Commented Mar 17, 2020 at 16:54
  • 2
    $\begingroup$ 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... $\endgroup$ Commented Mar 17, 2020 at 18:26
  • 2
    $\begingroup$ ... 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). $\endgroup$ Commented Mar 17, 2020 at 18:34
  • 5
    $\begingroup$ Have you looked at the list of recent preprints on ECCC? 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.) $\endgroup$
    – Clement C.
    Commented Mar 17, 2020 at 23:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – exfret
    Commented Mar 18, 2020 at 1:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.