Questions tagged [descriptive-complexity]
Descriptive complexity classifies problems based on how hard it is to express the problem in some logical formalism.
61 questions
1 vote
0 answers
100 views
Immerman-Vardi Theorem - Why does QPTIME = PTIME
I am in the middle of understanding the Immerman-Vardi Theorem for a Seminar at my Uni. I've read up on "Sections 1–3 of Immerman, N. 1986. Relational Queries Computable in Polynomial Time. ...
- 11
0 votes
0 answers
87 views
Does every PTIME property on graphs of bounded treewidth admit a definition in quantifier-free fixed-point logic with counting (qf-FP+C)?
Fixed-point logic with counting (FP+C) is known to capture PTIME on various classes of finite structures, including graphs of bounded treewidth. I am interested in whether this expressive power still ...
3 votes
0 answers
120 views
Connection between descriptive complexity and automata theory
Immerman's classic descriptive complexity result says that over ordered structures, $FTC = NL$ where $FTC$ is first-order logic with a transitive closure operator and $NL$ is non-deterministic ...
- 233
5 votes
3 answers
314 views
Why is order/choice an issue for a logic for PTIME
As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
- 51
1 vote
0 answers
58 views
Are classes of graphs represented by adjacency matrix ordered structures?
We know that FO[LFP] captures PTIME on the class of ordered structures. However, I have difficulties interpreting this result. From what I understand, it means that, given a constant, finite alphabet $...
- 11
-3 votes
1 answer
160 views
Can one do descriptive complexity theory using abstract state machines?
I learned about ASM recently and was interested how it could used for descriptive complexity theory. Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
- 325
6 votes
1 answer
304 views
Implicit characterization of sublogarithmic space
Let $SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine ...
- 1,244
3 votes
0 answers
97 views
Extending fagin’s theorem for #P (for arbitary structure)
While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures. This is a corollary from fagin’s theorem. I have read fagin’s ...
- 251
1 vote
0 answers
135 views
Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains
Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
- 342
5 votes
1 answer
145 views
Nonterminal descriptional complexity of regular languages
Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below. I am aware of an ...
- 421
38 votes
3 answers
4k views
Is Descriptive Complexity dead?
I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be ...
- 1,418
6 votes
1 answer
344 views
What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)
According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. ...
- 922
0 votes
0 answers
126 views
Does Descriptive Complexity techniques have the naturalisation barrier?
I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise? By naturalise I'm talking about the Idea of Natural ...
- 91
8 votes
1 answer
275 views
Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?
In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to?
- 311
11 votes
0 answers
250 views
Descriptive Complexity characterzation of BPP
We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any ...
- 1,291