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.

learn more… | top users | synonyms

6
votes
0answers
24 views

Different definitions of optimal decompressors

Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$. I recall the definition of the algorithmic complexity of a string ...
21
votes
3answers
819 views

Using Kolmogorov complexity as input “size”

Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$. Normally in the analysis of algorithms or computational complexity theory, we have some ...
1
vote
0answers
46 views

Entropy criterion of efficiency for (comparison using hashing)

I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects. E.g., "domain" is the set of valid english phrases with length ...
1
vote
2answers
90 views

Is there an $\mathcal{L}$-theory and a formula $\phi$ for which Kolmogorov(proof($\phi$)) $<$ Kolmogorov($\phi$)?

Are there a complete decidable $\mathcal{L}$-theory, a formula $\phi$ and a proof of $\phi$ for which the Kolmogorov complexity of the proof of $\phi$ is less than the Kolmogorov complexity of $\phi$? ...
6
votes
1answer
159 views

Kolmogorov Complexity of an arbitrary string

For an arbitrary string sampled from $\{0,1\}^n$, what would be the probability that the string has a Kolmogorov Complexity $\geq$ length of the string, $n$. In other words, how many strings are ...
8
votes
3answers
433 views

Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
0
votes
1answer
88 views

What information can a program give about the Kolmogorov Complexity of its accepting Language

Suppose we have a program(algorithm) that solves some decision problem $(\Sigma,L)$. Given the program, can we always say something about the Kolmogorov complexity of the words in $L$ ?
4
votes
3answers
556 views

How to measure programming language succinctness?

I want to explore the notion of quantifying the amount of succinctness a programming language provides. That is, the amount a high-level language reduces the complex. This idea of "simplification" ...
2
votes
0answers
40 views

Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: ...
6
votes
0answers
106 views

Complexity of Roman numeral evaluation

I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid: https://gist.github.com/4542999 1) Is this a known result? 2) If not, any ...
7
votes
1answer
192 views

Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as $\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), ...
3
votes
0answers
143 views

Is “normalized distance” (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?

In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the ...
20
votes
2answers
563 views

Circuit lower bounds and kolmogorov complexity

Consider the following reasoning: Let $K(x)$ denote the Kolmogorov complexity of the string $x$. Chaitin's incompleteness theorem says that for any consistent and sufficiently strong formal ...
3
votes
1answer
305 views

More complex integers

In connection to this question: Expected values of Kolmogorov complexity in a random sample Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > ...
1
vote
1answer
545 views

Definition of a prefix-free Turing machine

A prefix-free function is one whose domain is prefix-free. Similarly, a prefix-free (Turing) machine is one whose domain is prefix-free. It is usual to consider such a machine as being ...
0
votes
1answer
212 views

Non-computable=>normal?

If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite ...
18
votes
4answers
615 views

Efficiently computable variants of Kolmogorov complexity

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features: It corresponds to an intuition of giving strings with patters or ...
12
votes
2answers
254 views

Channel coding results using Kolmogorov complexity

Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov ...
6
votes
2answers
407 views

Expected values of Kolmogorov complexity in a random sample

Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ ...
11
votes
2answers
285 views

Kolmogorov complexity with weak description languages

We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like ...
5
votes
1answer
267 views

Average-case analysis of algorithms using the incompressibility method

I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many ...
5
votes
1answer
203 views

Time-bounded Kolmogorov complexity and non-random strings

If $t$ is a time constructible function then we can define the time-bounded Kolmogorov complexity of a string $x$ as: $C^t(x)$ = the size of the smallest program p that generates $x$ in $t(|x|)$ ...
10
votes
4answers
967 views

Is there a theory to answer “the simplest program to solve a problem”?

To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the ...
6
votes
4answers
418 views

Are there incompressible strings $S$ such that $K(SS) \lt K(S)$?

This question was inspired by Sune Jakobsen's question and Tsuyoshi's answer. In Kolmogorov-complexity, a string is incompressible if $K(S) \ge |S|$. Is there incompressible string $S$ such that ...
15
votes
3answers
533 views

Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.

Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)<K(x)$. (Here $xx$ is the concatenation of $x$ with itself). A similar but different question ...
3
votes
1answer
215 views

Kolmogorov complexity of D and D+d

I'm looking into using of the shelf compression algorithm to approximate the Kolmogorov complexity of a document corpus D and the complexity of D+d, where d is an extra document. I've got a strange ...
6
votes
1answer
121 views

Lower Bound on the difference between uniform and prefix-free complexity

The uniform Kolmogorov complexity (also known as decision complexity) of a string $\sigma$ is defined as follows: let $\phi: 2^{<\omega} \times \mathbb{N} \rightarrow {0,1}$ be a partial computable ...
4
votes
1answer
338 views

Definition of a monotone machine.

There is a definition of a 'monotone machine' in Li & Vitany's Book, and another one which is for example stated in this paper via c.e. (computably enumerable) sets. I can't see why these ...
9
votes
1answer
196 views

Worlds Relative to Which “Invulnerable Generators” Do Not Exist

Invulnerable generators are defined as follows: Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it ...
8
votes
1answer
439 views

Using Kolmogorov complexity to establish proof complexity lower bounds?

The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. ...