22
$\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$ – Joshua Grochow Nov 27 '20 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$ – Michael Wehar Nov 29 '20 at 20:24
  • $\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$ – Bartosz Bednarczyk Nov 30 '20 at 21:40
19
$\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$
1
  • 1
    $\begingroup$ Perhaps also this. $\endgroup$ – Yuval Filmus Nov 28 '20 at 9:31
10
$\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$ – Yuval Filmus Nov 28 '20 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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