Questions tagged [kolmogorov-complexity]

The Kolmogorov complexity of a string s is equal to the length of the shortest program computing s and halting. Measures the lack of structure in a string.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
82 views

Interval density of time bounded Kolmogorov complexity

The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
3
votes
0answers
45 views

Computability of Kolmogorov complexity in total languages

It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages? For example, is the Kolmogorov complexity of ...
3
votes
0answers
32 views

How do you resolve this paradox with the invariance theorem?

The invariance theorem of kolmogorov complexity states that for two different languages with complexity functions $K_1$ and $K_2$, we have $$\exists c.\forall s. K_1(s) \le K_2(s) + c$$ Here is an ...
2
votes
0answers
18 views

On teaching Kolmogorov complexity with Python and the complexity of composed strings

The setting of this question is a bit long-winded, but please bear with me. This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
2
votes
0answers
27 views

Is there a universal metric of “size of a program”?

There is a universal metric of information: amount of bits. It's universal in the sense that if we write a piece of information in DNA (4-ary digits), we can simply multiply by 2-log-4 to get the ...
2
votes
0answers
79 views

If a bitstring is compressible, is the minimal Kolmogorov sufficient statistic most likely large or small?

If a bitstring is incompressible, then its minimal Kolmogorov sufficient statistic (MKSS) is zero, since the bitstring is best represented by a structure function that enumerates bitstrings, and thus ...
2
votes
0answers
149 views

Relationship between algorithm size and compression power

Does the size of an algorithm restrict how many bitstrings it can compress, and how much it can compress the bitstrings? Some definitions and an example to illustrate this is the case. An elite ...
2
votes
0answers
77 views

What are the substitues for Kolmogorov Complexity to analyse Hashing

The paper "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses" <http://www.itu.dk/people/pagh/papers/sparse.pdf> is the only one that uses Kolmogorov Complexity to obtain ...
2
votes
0answers
51 views

How approximable is time-bounded Kolmogorov Complexity?

Given a Turing Complete Language, the optimization problem would be: Given inputs x and S, where x is a finite binary string and S is a limit on steps, find the shortest program in that TC language ...
2
votes
0answers
125 views

Universal lower semicomputable semimeasure and Coding Theorem

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question. The authors define the reference ...
2
votes
0answers
86 views

What are the simplest known algorithms to compute PI?

There are many algorithms that compute PI. Some are obviously complex, involving huge formulas and constants. Some formulas are not that complex, but involve operators such as ...
1
vote
0answers
17 views

Kolmogorov complexity of $y$ given $x = yz$ with $K(x) \geq \ell(x) - O(1)$

I am trying to solve Exercise 2.2.2 from "An Introduction to Kolmogorov Complexity and Its Applications" (Li & Vitányi, vol. 3). The exercise is as follows (paraphrased): Let $x$ satisfy $K(x) \...
1
vote
0answers
16 views

Is there a hierarchy theory for time-bounded Kolmogorov complexity?

We know that there are languages in $DTIME(n^t)$ and not in $DTIME(n^s)$ for all $t>s$ due to simple diagonal arguments (i.e., the Time Hierarchy Theorem), but I'm wondering if there is any ...
1
vote
0answers
179 views

VC Dimension of A Set of Hypothesis

I am confused about what does a VC dimension of a set of hypothesis means. I have two hypothesis, say $H_1$ with VC dimension of $x$, and $H_2$ of VC dimension of $y$. Does this automatically mean ...
1
vote
0answers
24 views

United space-time complexity of finite strings

Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example ...
1
vote
0answers
32 views

What do you call a set which has the following enumeration-related machine?

A set $S$ of natural numbers is Recursively Enumerable if there exists a Turing machine which enumerates them, i.e. given no input, outputs the elements of $S$ in increasing order (never halting if $...
1
vote
0answers
106 views

Kolmogorov complexity of a random string conditioned on another random string

Given two strings $x$, $y$, both of length $n$, what is the probability that $K(x|y,n)=K(x|n)$ ? (Bounds on this probability would be very interesting too). Here $K$ is Kolmogorov complexity, $x$ and $...
1
vote
0answers
73 views

Conditional Kolmogorov compexity of string concatenation

In what follows $K(x|y)$ is conditional Kolmogorov complexity, $xx$ is $x$ concatenated with itself. It appears to me that $K(xx|yy)=K(xx)$ should be true for infinitely many strings $x$ and $y$. In ...
1
vote
0answers
42 views

Joint Kolmogorov complexity of elegant programs

If $a$ and $b$ are different elegant programs (minimal program for some output), is their joint Kolmogorov complexity the sum of their individual complexities, i.e. $K(a,b) = K(a) + K(b)$?
0
votes
0answers
31 views

Are real computers capable of producing true random series with a program of finite length?

Suppose that one has a Blum–Shub–Smale machine. Is it possible to write down a program of finite length that produces a series of numbers, with each consisting of a finite number of digits, such that ...
0
votes
0answers
18 views

How does neural net complexity relate to other complexity measures?

In neural networks, "weight regularization" is often used as a so called "complexity penalty" in order to make sure that the network generalizes better from training data. Similarly, in "program ...
0
votes
0answers
19 views

Perturbative Kolmogorov Complexity Bounds

Are there any known bounds on the impact of changing (for example) one bit in a string on the resulting string's Kolmogorov Complexity? In mathematical terms, does the equation $|K(x) - K(x')|$ (with $...