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?
$\begingroup$
$\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 GrochowNov 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$– Michael WeharNov 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$– Bartosz BednarczykNov 30, 2020 at 21:40
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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:
- Rank logics:
- Rank Logic is Dead, Long Live Rank Logic! by Grädel and Pakusa
- Symmetric Circuits for Rank Logic by Dawar and Wilsenach
- Separating Rank Logic from Polynomial Time by Lichter
- Choiceless Polynomial Time:
- Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time by Lichter and Schweitzer
- Choiceless Logarithmic Space by Grädel and Schalthöfer
- Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs by Dawar et al.
- Dynamic Complexity:
- Dynamic Complexity of Parity Exists Queries by Vortmeier and Zeume
- Reachability Is in DynFO by Datta, Kulkarni, Mukherjee, Schwentick and Zeume
- PHD thesis of Thomas Zeume
- Other interesting things:
- Descriptive Complexity for Counting Complexity Classes by Arenas Muñoz and Riveros
- Descriptive complexity of real computation and probabilistic independence logic by Hannula, Kontinen, Van den Bussche and Virtema
- Descriptive Complexity of Deterministic Polylogarithmic Time by Ferrarotti et al
- On the Power of Symmetric Linear Programs by Atserias, Dawar and Ochremiak
- Traversal-invariant characterizations of logarithmic space by Bhaskar, Lindell and Weinstein
The list is not supposed to be complete. Just giving you a glimpse on what kind of problems are people looking at.
answered Nov 27, 2020 at 17:03
-
2
-
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$ 18 hours ago
$\begingroup$
$\endgroup$
1
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}$.
answered Nov 27, 2020 at 17:13
-
2
$\begingroup$
$\endgroup$
0
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.)
