# 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

26 questions
Filter by
Sorted by
Tagged with
52 views

### Inexpressibility results in $FO+LFP$

When we want to prove that some property is not expressible in certain logic, we often use EF-game or it's variants to show this result in finite model theory. for example, we can show that ...
• 33
323 views

### Kolmogorov Complexity and Compression Schemes

My question concerns strings with low Kolmogorov Complexities and if there is a single compression scheme that can be used to compress them I have been introduced to Kolmogorov Complexity through ...
• 256
1 vote
36 views

### Has it been proven that second order statements cannot be computed in polynomial time? Can some statements be proven to only be second order expresibl

I have read about the Immerman Vardi theorem and I do not understand what the implications fully are. Does it say that second order logic cannot be expressible in polynomial time? Or merely that all ...
26 views

### How To Get Subset Behavior In A Sum?

I'm studying a process where I am having to take a sum of integrals across parallelograms with various offsets based on sums of powers of $\frac{1}{3}$. So for instance, at Level $k=2$ of the process, ...
183 views

### Applications of Model Theory and Category Theory

Do Model Theory and Category Theory have applications in solving Complexity and Game Theory problems in computer science? I am looking for an example of these...(If there is any...)
• 859
383 views

### Number of possible boolean functions in a DAG of lookup tables?

A K-input lookup table (K-LUT) can represent any function with K boolean inputs and a single boolean output. The number of possible functions represented by this LUT is $2^{2^K}$ according to this ...
• 59
61 views

### Show that set of words in NP

Let 𝐴 ∈ NP. How can I show that the set of all cyclic permutations of words from 𝐴 also lies in NP The issue I have with this task is that I cannot understand the correlation of cyclic permutation ...
• 115
88 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 ...
67 views

• 18.2k
75 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. ...
• 18.2k
1 vote
70 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 ...
• 18.2k
1 vote
60 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 ...
• 133
1 vote
53 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 ...
• 4,216
651 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 ...
• 444
47 views

### "linear order" in descriptive complexity description of class P

In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. So, what does "linear order" mean here?
• 3