34
$\begingroup$

I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite old. Seems like this line of research is dead. Is this the case? If so, why?

$\endgroup$
3
  • 2
    $\begingroup$ While some questions are particular to descriptive complexity, for many other descriptive complexity simply offers an alternative characterization of other things (e.g. Fagin's Theorem). That alternative characterization can be a useful viewpoint for some people to make progress or ask interesting questions that wouldn't have been thought of with a different viewpoint. So regardless of it is dead or not as a research area in & of itself, it could still be useful to learn that viewpoint. $\endgroup$ Nov 27, 2020 at 17:15
  • $\begingroup$ Isn't there a conference every year on the descriptional complexity of formal systems (DCFS) or is this something different from what you meant? Link: informatik.uni-giessen.de/dcfs/proceedings.html $\endgroup$ Nov 29, 2020 at 20:24
  • 4
    $\begingroup$ I believe that descriptional complexity and descriptive complexity are different branches of mathematics. Descriptional complexity is about finding the bounds on the size of an automaton recognizing some language while descriptive complexity is about finding a logic that characterizes some complexity class. $\endgroup$ Nov 30, 2020 at 21:40

3 Answers 3

30
$\begingroup$

I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active:

  1. Rank logics:
  1. Choiceless Polynomial Time:
  1. Dynamic Complexity:
  1. Other interesting things:

The list is not supposed to be complete. Just giving you a glimpse on what kind of problems are people looking at.

$\endgroup$
3
  • 2
    $\begingroup$ Perhaps also this. $\endgroup$ Nov 28, 2020 at 9:31
  • 2
    $\begingroup$ An important paper just appeared on arxiv (accepted to LICS 2021): Separating Rank Logic from Polynomial Time. I updated the references. $\endgroup$ Apr 28, 2021 at 15:46
  • 2
    $\begingroup$ From 2008: doi.org/10.1016/j.apal.2007.11.011 Dawar, Richerby, & Rossman Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs. $\endgroup$ Nov 30, 2023 at 17:01
15
$\begingroup$

Definitely still active in the area of Weisfeiler-Leman-style algorithms for isomorphism problems such as Graph Isomorphism. The connection with logic was first (I believe) made in Immerman-Lander and Cai-Fürer-Immerman. Very recently adapted to Group Isomorphism [Brachter-Schweitzer]. Certain logics are equivalent in their power to distinguish graphs (resp. groups, etc.) to the WL family of algorithms.

Properties of Weisfeiler-Leman, and hence, equivalently, of the corresponding logics, are still an active area of research, e.g. see these few papers from the past few years as well as this conference on its 50th anniversary.

Also, a polynomial-time graph canonization algorithm would solve the long-standing question of a logic that captures $\mathsf{P}$.

$\endgroup$
1
  • 2
    $\begingroup$ Perhaps also this. $\endgroup$ Nov 28, 2020 at 9:31
2
$\begingroup$

Since Immerman's book was published, a few other books have come out.. (But they may have "Finite Model Theory" in their titles.)

"Lot of hope at the beginning, but then not much happened" --- this has been the case with several approaches in Computational Complexity.. So we cannot (or should not) single out Descriptive Complexity for blaming.

In terms of its application:

"Consider Problem $A$.. We show that it can be expressed in Logic $B$.. And hence, it follows that its computational (or approximation) complexity is $C$" --- How many new results have been published along these lines? $~$ Not many, to my knowledge.. (But I'm happy to be proven wrong.)

$\endgroup$
0

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.