# Questions tagged [descriptive-complexity]

a subfield of computational complexity. Instead of creating a program, logical operators, like quantifiers and least fixed point, are used to categorize problems

19 questions
Filter by
Sorted by
Tagged with
24 views

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 ...
64 views

### Coarsenings of the topology on $2^\omega$ with $F_\sigma$ (sub)base

Motivation: I am interested in computational representations of topological spaces which are particularly "explicit", in the somewhat vague sense that we can specify everything we care about ...
59 views

51 views

### Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the string. ...
61 views

### On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
46 views

### What to study to learn descriptive complexity?

I have an assignment to study the descriptive complexity of a given device that is described with some algebra and informal statements. I have a background in computer engineering but I haven't ...
42 views

### Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
449 views

### A question on Kolmogorov Complexity

Is it true that for all strings of a given length at least one has its Kolmogorov complexity equal to its length ? Is there a proof if the answer is in affirmative? (For any alphabet with more than ...