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.

Filter by
Sorted by
Tagged with
2
votes
2answers
303 views

Computing the Kolmogorov complexity of a string

What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?
2
votes
1answer
88 views

An infinite subsequence of random numbers in Kolmogorov sense

Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. ...
2
votes
1answer
48 views

(operationalizable) Cost measure for small problems

For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they ...
2
votes
1answer
228 views

Is the length of the shortest quine in a programming language computable?

The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of ...
2
votes
1answer
86 views

What doest it mean: “computer is an intelligence amplifier”?

There is one example in Kolmogorov complexity books and related articles: Consider we have a monkey at a typewriter and a monkey at a computer keyboard. If the monkey types at random on a typewriter,...
2
votes
1answer
95 views

Unrolling closures into SAT boolean formula

I need to verify some assertions about the minimalist Turing-complete language Jot. Many of the assertions I want to investigate are semi-deciable (co-recursively enumerable). So far it's been fairly ...
2
votes
1answer
109 views

Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?

If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?
2
votes
0answers
214 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
23 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 ...
2
votes
0answers
29 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
161 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
86 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
56 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
141 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
91 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 ...
2
votes
1answer
199 views

Kolmogorov complexity of strings in a given language

Consider the language $$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$ and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be ...
1
vote
1answer
89 views

How can I prove the languages of incompressible words is undecidable?

I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ". The proof is as follows : M' = " On input $n$ Enumerate over all $n$-...
1
vote
1answer
117 views

Examples of exact computation 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 ...
1
vote
1answer
76 views

Prove that A is non-regular using K-Complexity Non regularity theorem

Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$ Given $A \subseteq ...
1
vote
1answer
27 views

Is $K(b|a) \geq 1$ if $a\neq b$?

Since $K(a|a) = 0$, is $K(b|a) \geq 1$ when $a\neq b$, as we need at least one bit to distinguish between $K(a|a)$ and $K(b|a)$? If not true in general, is it true if $a$ and $b$ are elegant programs?...
1
vote
1answer
109 views

Is a bitstring easier to compress if it has lower Kolmogorov complexity?

I have two bitstrings that are 100 bits long. Bitstring A has a Kolmogorov complexity (KC) of 90 and bitstring B has a KC of 10. Intuitively, I think bitstring B is probably easier to compress than ...
1
vote
1answer
64 views

How can Kolmogorov complexity help me practically with measuring entropy?

A comment was made to me saying the following in relation to Kolmogorov complexity:- You're not the first to think non-computability = impractical or even useless. But it can be useful. In particular ...
1
vote
1answer
51 views

Kolmogorov complexity of a sequence of n bits with k ones

Let Program P be :"Generate, in lexicographic order, all sequences with k ones and n bit length; Of these sequences, print the ith sequence." Apparently the length of this program is $\log(n) + \log(\...
1
vote
1answer
150 views

Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)

When proving a language is non regular we can use Kolmogorov complexity. As far I know to do this we just have to use this satisfy the following conditions Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (...
1
vote
1answer
518 views

How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem

I try to solve the following exercise: We know that K (x), the complexity of Kolmogorov, is incomputable. Show how calculate it, if we have an oracle for the membership problem (or for the HALT ...
1
vote
1answer
209 views

When is conditional Kolmogorov complexity zero?

It seems intuitive that conditional Kolmogorov complexity is only zero when the bitstrings are the same, and otherwise is greater than 0. I.e. if $b_1 = b_2$, then $K(b_1|b_2) = 0$, otherwise $K(b_1|...
1
vote
1answer
50 views

What is The correct terminology for expressing *this* notion of complexity

Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set ...
1
vote
1answer
36 views

For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases

Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let g() { f(v) } be the ...
1
vote
1answer
130 views

Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$

I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here ...
1
vote
0answers
32 views

Kolmogorov-Complexity of strings in decidable languages

I just recently learned about Kolmogorov-Complexity and had an idea for giving an upper bound for strings in a decidable language. Is the following statement true? Say we have a recursive language. ...
1
vote
1answer
43 views

A property of Kolmogorov random strings

I am working on the following problem: Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\{0,1\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ ...
1
vote
1answer
31 views

Expressivity of neural networks, how much information can be stored

I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps ...
1
vote
0answers
34 views

Kolmogorov complexity of a product of two numbers

In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal ...
1
vote
1answer
53 views

Kolmogorov Complexity, struggle with equation

I am working on understanding Kolmogorov Complexity. I've been struggling with the following exercise for quite some time now and would appreciate any inputs. Show that there exists a constant $c$, ...
1
vote
0answers
225 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
26 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
119 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
91 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
53 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
2answers
102 views

Is Kolmogorov Complexity Universal?

Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information? ...
0
votes
1answer
48 views

How to define enumeration of the set of finite state machines?

I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
0
votes
1answer
34 views

Computability of Kolmogorov Complexity of Turing-Incomplete language

I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows: $A;B \text{ - ...
0
votes
1answer
58 views

Kolmogorov randomness for Pseudo random number generator

I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate ...
0
votes
1answer
50 views

Kolmogorov complexity of prefixes of computable sequences

Let the characteristic sequence of a set $A ⊆ \mathbb{Z^+}$ be the following infinite binary sequence: $$χ_A = b_1b_2b_3\ldots,$$ whose $n$th bit is 1 if $n ∈ A$ And 0 otherwise. Write $χ_{A,n}$ for ...
0
votes
0answers
22 views

How many strings of length |w| are unrelated?

For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated? A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...
0
votes
0answers
31 views

Are SKI combinators an optimal language with respect to Kolmogorov complexity?

Let's say we have a language that decodes a bitstring in this way: ...
0
votes
0answers
25 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 $...

1
2