# Tag Info

Accepted

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 ...
• 1,337

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 ...
• 37.3k

### 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 ...
• 17.4k
Accepted

### 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 ...
• 14.5k

### 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 ...
• 4,630

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)}}]... • 146 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: ... • 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 ... • 21.6k 3 votes Accepted ### 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 ... 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=... • 6,470 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 ... • 171 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. ... • 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 ...
• 411

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 ...
1 vote
Accepted

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

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