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
3
votes
0
answers
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
3
votes
1
answer
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
0
answers
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 ...
- 11
0
votes
0
answers
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, ...
- 75
3
votes
1
answer
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
0
votes
1
answer
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
0
votes
1
answer
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
2
votes
0
answers
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 ...
- 934
2
votes
1
answer
67
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^{\...
- 16.6k
0
votes
2
answers
48
views
Does ((L=NP) and (PH=PSPACE)) imply (FO=SO)? Is (L=/=NP) or (PH=/=PSPACE)?
First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space.
[1] L = FO with commutative transitive closure operator.
...
- 520
1
vote
0
answers
94
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
0
answers
38
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 ...
- 303
0
votes
2
answers
61
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 ...
- 103
4
votes
2
answers
225
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 ...
- 43
2
votes
1
answer
744
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 ...
-1
votes
1
answer
111
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 ...
- 4,475
0
votes
0
answers
108
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?
- 1,211
2
votes
1
answer
257
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 ...
- 18.2k
2
votes
0
answers
31
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 $...
- 18.2k
3
votes
0
answers
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
0
answers
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
1
answer
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
0
answers
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
2
votes
1
answer
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
0
votes
1
answer
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
2
votes
1
answer
193
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 ...
- 905