# 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,110

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

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

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

### 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,501
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 ...
• 1,096

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

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