26 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
13 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

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
6 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.2k
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
  • 494
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.4k
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

What do dichotomy theorems feed on?

For the case of Schaefer's dichotomy theorem, informally, the universal expressive power of Boolean CNF formulas built from non-Schaefer logical relations is behind the dichotomy. Every logical ...
Mohammad Al-Turkistany'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

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

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

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
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