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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)}}]...
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 ...
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:
...
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 ...
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 ...
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 ...
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 ...
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.
...
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=...
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 ...
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
Related Tags
descriptive-complexity × 53cc.complexity-theory × 28
lo.logic × 24
finite-model-theory × 16
complexity-classes × 7
proof-complexity × 4
ds.algorithms × 3
reference-request × 3
graph-theory × 3
graph-algorithms × 3
fl.formal-languages × 3
automata-theory × 3
computability × 3
db.databases × 3
co.combinatorics × 2
quantum-computing × 2
circuit-complexity × 2
regular-language × 2
context-free × 2
terminology × 2
kolmogorov-complexity × 2
conditional-results × 2
model-checking × 2
first-order-logic × 2
type-theory × 1