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 ...
- 1,110
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 ...
- 35.8k
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 ...
- 14.8k
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 ...
- 14.8k
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 ...
- 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 ...
- 4,501
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 ...
- 1,096
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)}}]...
- 136
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 ...
- 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:
...
- 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 ...
- 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 ...
- 121
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 ...
- 20.6k
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 ...
- 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.
...
- 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=...
- 5,444
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
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 ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible