I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I don't mean that other are not) in terms of number of research papers. I have seen that researchers from communication complexity, arithmetic complexity etc. are also using various parameters to greater extent.

Question : Is parameterized complexity going to be the future of complexity theory? Future just means number of research papers, number of researchers working in that area etc.

Please note that I am naive and may not be aware of many things.

  • 3
    $\begingroup$ I think only really your second question is suitable for this site - namely, are there works on "quantum parametrized complexity"? - as the first question is (a) about predicting the future, which is always hard, and (b) the answers would be very subjective. But I suspect the answer to your question (1) is that there is still lots of active research in algorithms and complexity that is not about parametrized complexity. $\endgroup$ Feb 25, 2018 at 17:02
  • 1
    $\begingroup$ Non-researcher here, but I never knew parameterized complexity was a different thing than just... complexity. What exactly did people do beforehand when a complexity depended on two quantities? Just forget one of them? $\endgroup$
    – user541686
    Feb 25, 2018 at 22:10
  • 1
    $\begingroup$ I'm a big fan of parameterized complexity and I was excited to see this post on the same day that the FPT newsletter came out. :) $\endgroup$ Feb 26, 2018 at 7:17

1 Answer 1


Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over by indistinguishability obfuscation.

That said, I will say this much: I don't see any particular reason to expect parameterized complexity to take over. It's a mature field that has been active for something like 20 years. It doesn't really strike me as an up-and-coming area. To be clear, I think it's a successful area that will continue to thrive.

If you look on google trends, search interest in parameterized complexity has been declining. (Stick in some other terms for a comparison if you're interested.) If you look up the combined citations for the Downey-Fellows textbook Parameterized Complexity and their updated textbook, you see that they are pretty stable: enter image description here (Source: Google scholar. I added both books to my own profile, merged them, took a screenshot of the combined citations, and then deleted them from my profile.)

This is a healthy number of citations, but it is not the exponential growth that would make you think parameterized complexity is going to take over. Of course, this data is very flawed, but it's the best indication I can find of the global popularity of parameterized complexity.

Note that things can be very popular locally even if they aren't popular globally. When I was an undergrad, I thought that I needed to learn about category theory because everyone around me was talking about it; I even bought a book. Then I moved on to grad school and never heard about it again; the book remains unread to this day. Perhaps you are in a similar situation -- you are in a department where there is a lot of parameterized complexity going on, but, if you move somewhere else, the story will be completely different.

  • 6
    $\begingroup$ RIP to all those unread category theory books out there... $\endgroup$ Feb 26, 2018 at 0:25
  • 3
    $\begingroup$ Just out of curiousity: are you saying that there was a place where a number of people working in complexity and algorithms were interested for some time in category theory? Or were these people more in the programming languages world? (In which case it would not be surprising). As a category-theory-oriented researcher, I am quite curious to know where this place was and what was the interest about. $\endgroup$ Feb 26, 2018 at 11:29
  • $\begingroup$ @DamianoMazza I got into algorithms and complexity in grad school. My exposure to Category theory was on the PL/logic side of things. I do like category theory; it just hasn’t come up much in my work. $\endgroup$
    – Thomas
    Feb 26, 2018 at 16:38
  • $\begingroup$ Ok, as I said, it's not very surprising then! (Neither that PL/logic people are interestest in categories, nor that you haven't found a use for them in algorithms and complexity). Thank you! $\endgroup$ Feb 27, 2018 at 18:26
  • $\begingroup$ @DamianoMazza you can make a “pseudo-category” of TMs and quotient it by some weak reducibility and then you get nice things like the ability to characterize completeness via category theoretic constructions, but it seems to me when I’ve done it that you get exactly the same outcomes by just using a poset. There’s this paper which was posted on here a while ago making this connection: principal ideals in this poset form “syntactic classes”, which have a complete language and are countably enumerable. Maybe there is more mileage you can get from a suitable category, I haven’t gotten any though. $\endgroup$ Mar 18, 2018 at 16:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.