26 votes
Accepted

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 ...
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 ...
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 ...
user avatar
8 votes

Completeness of the extension of first order logic with least fixed point order operator

FO-LFP is neither complete (its valid sentences cannot be described by a recursively presented proof system) nor compact (there is an unsatisfiable set of sentences all of whose finite subsets are ...
user avatar
6 votes
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 ...
user avatar
  • 14.1k
6 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 ...
user avatar
6 votes
Accepted

Expressiveness of Infinitary Logic

There is a famous example of Cai, Fürer and Immerman, which shows that the $\mathcal{C}_{\infty\omega}^k$-hierarchy is strict and in particular that $\mathcal{C}_{\infty\omega}^\omega$ cannot express ...
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)}}]...
user avatar
4 votes

Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

Here's a more reality-concerned version of tigreen's answer from the point of a person who actually makes heavy use of (relational) databases: The whole point and complexity of their application is to ...
user avatar
  • 141
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: ...
user avatar
  • 464
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 ...
user avatar
  • 21.3k
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 ...
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 ...
user avatar
2 votes

Completeness of the extension of first order logic with least fixed point order operator

It does not extend. Consider FO-LFP with just a binary predicate $<$, and the axioms for $<$ being a total order, with first and last positions, and every position has a successor. Moreover, we ...
user avatar
  • 7,653
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. ...
user avatar
  • 21
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=...
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 ...
user avatar
  • 411
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. ...
user avatar
  • 842
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 ...
user avatar

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