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

Filter by
Sorted by
Tagged with
0
votes
0answers
24 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
vote
0answers
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 ...
2
votes
1answer
59 views

Complexity of formulae involving projective sets in Polish spaces

I am no expert in descriptive set theory, but for some reason want to estimate the complexity of a certain formula. The framework. Let be $F$ a projective set in the Polish space $X=\mathbb R^{\...
1
vote
0answers
50 views

Computing the Sum of Log n Bits in First Order Logic

I have read the so-called Bit-Sum Lemma from Neil Immerman. "Descriptive Complexity" (Lemma 1.18) and from Barrington, Immerman and Straubing. "On uniformity within $NC^1$" (Lemma 7.2) but I am ...
0
votes
0answers
29 views

algebras for extensions of FO and existential SO

As cylindric algebra is the algebraization of FO with equality: How can be this algebra extended s.t. ESO is captured by it, e.g. how to algebraize quantifications of relation variables? How can one ...
0
votes
2answers
35 views

Is there an algorithmic complexity measure that strikes a balance between regularity and randomness of a string?

If my understanding is correct, Kolmogorov complexity would assign the highest value (description length) to a totally random string, such as: abewdwflkweoasfksalsfnlka the lowest value to a ...
3
votes
2answers
81 views

Any examples of exact calculation of Kolmogorov Complexity??

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed ...
2
votes
1answer
194 views

How many different graphs of order $n$ are there?

I'm interested in all four combinations: directed and undirected, cyclic and acyclic. I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number ...
0
votes
1answer
90 views

What is algebra with the most structure? [closed]

If you agree that complex numbers are more "complicated" than real numbers, and quaternions are more "complicated" then the complex numbers. What currently known is the most complicated algebra? I ...
0
votes
0answers
74 views

Proof complexity and computational complexity

What is the relation between proof complexity and computational complexity (Turning machine)? Is there any reference around these stuff?
2
votes
1answer
104 views

The problem $K(x) \le K(y)$ is not decidable for Kolmogorov complexity $K$

Let $X$ be some finite alphabet. Given $(x,y) \in X^{\ast}\times X^{\ast}$, how to show that $K(x) \le K(y)$ is not decidable? I know that $K(x) \le k$ for some fixed $k$ is not decidable, so I tried ...
2
votes
0answers
23 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all $...
3
votes
0answers
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. ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
34 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?
2
votes
1answer
155 views

LFP - shortest path problem

Curious question: Can anyone show me how to describe shortest path problem using LFP + first order logic? I am just getting lost on how to describe the problem, though I know that LFP + first-order ...