30 votes

Is Descriptive Complexity dead?

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 ...
Bartosz Bednarczyk's user avatar
15 votes

Is Descriptive Complexity dead?

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 ...
Joshua Grochow's user avatar
11 votes

Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?

As you move to higher-order logics, each new order gives you quantification over exponentially larger objects than before, thus you can simulate exponentially longer computations. Other than that, it ...
Emil Jeřábek's user avatar
7 votes

Where does the "intuitive" understanding of Kolmogorov complexity fails

The issue in play here is whether you use a self-terminating encoding (like your C example) or not. If you use a self-terminating encoding, then the subadditivity property does hold. If you don't (as ...
Yuval Filmus's user avatar
  • 14.4k
7 votes

Reductions in Descriptive Complexity

Standard notions of reduction used in Descriptive Complexity are first-order reduction and the weaker first-order projection. Definitions of both these notions are found in Immerman's book on ...
Jan Johannsen's user avatar
5 votes

Descriptive model theory classification of Counting hierarchy

This is only a partial answer (to the $PSPACE$ characterization), but I don't have the reputation to comment. $PSPACE$ has the following (equivalent) descriptive characterizations: $FO[2^{n^{O(1)}}]...
Sam McGuire's user avatar
4 votes

What is First-Order Rewritable (and FO-Query)?

Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem: ...
mak's user avatar
  • 504
3 votes

Construct proof systems for common algorithmic task, like equivalence of regular expressions

You have a non-deterministic algorithm deciding the problem. If you want to think of it as a proof system for $EQUIV$, then the proof of $(u,v) \in EQUIVE$ is just the string representing the ...
Kaveh's user avatar
  • 21.6k
3 votes

reference request: deciding validity of higher-order quantified boolean formulas is not Kalmar-elementary

One can be more precise than "non-elementary" and say that HOQBF is TOWER-complete — morally, TOWER is the complexity class just beyond elementary. This fact is explicitly stated and proved ...
Lê Thành Dũng Nguyễn's user avatar
2 votes

P and Descriptive Complexity

Martin Grohe made substantial progress on this question recently. He gives a logic capturing polynomial time on classes of graphs embeddable in a fixed surface: https://dl.acm.org/citation.cfm?doid=...
Hermann Gruber's user avatar
2 votes

Construct proof systems for common algorithmic task, like equivalence of regular expressions

Kaveh's response exemplifies well the Cook-Reckhow notion of an abstract proof system. Nonetheless, for comparison, I point to a recent preprint of mine and Damien Pous: A cut-free cyclic proof ...
Anupam Das's user avatar
2 votes

Understanding least-fixed point logic

this is a very old post so you might have already encountered the answer as desired. Since I have been studying FO(LFP) for the past few months. I have some understanding of the answers you require. ...
Ramit's user avatar
  • 21
2 votes

Nonterminal descriptional complexity of regular languages

Lemma 1. Consider $L = (ab)^* + (ba)^*$: There exists CFG with two variables which generates $L$ There exist no CFG with one variable which generates $L$ For proving (1) we may just consider the ...
DG_'s user avatar
  • 411
2 votes

Is Descriptive Complexity dead?

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 ...
Shuxue Jiaoshou's user avatar
1 vote

What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)

Professor Immerman kindly answered this by email: The definition of FO(REGULAR) is the set of all decision problems that are reducible to some regular language via first-order reductions. ...
Caleb Stanford's user avatar
1 vote

What is First-Order Rewritable (and FO-Query)?

As a complement to Janoma's answer above: it's 'very good'--- from the point of view of implementation --- because given a FO-rewritable language, we can use the powerful engines (for evaluating ...
Julio Lemos's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible