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.
81
questions
29
votes
5answers
2k 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 ...
28
votes
2answers
1k views
Can we not output the Kolmogorov complexity?
Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ...
22
votes
2answers
848 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 ...
21
votes
3answers
1k 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 ...
17
votes
1answer
779 views
Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?
Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. -...
16
votes
3answers
988 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 ...
14
votes
1answer
479 views
Comparing the Kolmogorov complexity of theories
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(s) > L$ where $K(s)$ is the Kolmogorov complexity of string $s$ and $L$ is a sufficiently large ...
13
votes
2answers
396 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 (local)...
12
votes
2answers
468 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 ...
11
votes
1answer
636 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. ...
10
votes
3answers
1k 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 ...
10
votes
1answer
254 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 ...
9
votes
2answers
631 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}$ ...
9
votes
1answer
359 views
Is Kolmogorov complexity a surjective function?
Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever).
Define the Kolmogorov complexity ...
9
votes
3answers
980 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 ...
8
votes
2answers
3k views
Proof for Kolmogorov complexity is uncomputable using reductions
I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
8
votes
1answer
204 views
Is Kolmogorov complexity quasi-surjective?
For Kolmogorov complexities $\hspace{.02 in}K$ induced by essentially-optimal description languages,
does there exist an integer $c$ such that for all positive integers $n$,
there exists a string $x$...
8
votes
1answer
136 views
Inferring the Kolmogorov complexity of a string from its substrings' complexity
I know that the Kolmogorov complexity of a substring $v$ of an incompressible string $x$ has $C(v)\geq |v|-O(\log{|x|})$ , but I'm wondering if it is also possible to infer the complexity of a string ...
8
votes
0answers
152 views
Number of circuits computing a given function
Let's say we have some function that can be computed by a minimal circuit of size $m$ (using some metric, say, the number of gates). Other than this minimal circuit, there will be many other circuits ...
7
votes
1answer
375 views
Where does the “intuitive” understanding of Kolmogorov complexity fails
Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.
So to give this more formal meaning, define
$$
K'(x) := ...
7
votes
1answer
291 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 ...
7
votes
1answer
278 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), ...
7
votes
1answer
379 views
Difference between time-bounded and memory-bounded Kolmogorov complexity
Let $x$ be a finite string of length $n$.
Denote by $C^t(x)$ the Kolmogorov complexity of $x$ bounded by time $t$ (i.e. the length of a minimal program that outputs $x$ and running at most $t$ steps)....
6
votes
1answer
344 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 ...
6
votes
2answers
2k 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
self-...
6
votes
1answer
315 views
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.
Background/Motivation: Coming ...
6
votes
1answer
267 views
Expected Kolmogorov complexity under Kolmogorov complexity distribution
If $K(w)$ is the Kolmogorov complexity of a string $w$, where programs are prefix-encoded so $\sum_{w} 2^{-K(w)} \leq 1$, what is
$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} K(w)}{\sum_{|w|=n} 2^{...
6
votes
1answer
389 views
Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?
Chaitin's incompleteness theorem states for any formal system $F$ (which satisfies various criteria), there is a $L$ such that for any $s$ the statement $$K(s) \ge L_F$$ is unprovable in that formal ...
6
votes
1answer
244 views
Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic
Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$.
A bitstring $B$ is generated by drawing 0s and 1s ...
6
votes
1answer
350 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|)$ ...
6
votes
1answer
641 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 ...
6
votes
1answer
148 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 ...
6
votes
4answers
580 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 $K(...
6
votes
0answers
160 views
What is the Kolmogorov complexity of arithmetic?
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(n) > L$ where $K(n)$ is the Kolmogorov complexity of the number $n$ and $L$ is a sufficiently large ...
6
votes
0answers
143 views
Comparing the Kolmogorov complexity of theories - Part 2
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
6
votes
0answers
35 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 ...
6
votes
0answers
180 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 ...
5
votes
3answers
1k 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" ...
5
votes
1answer
146 views
Kolmogorov Complexity of a Decidable Language
The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
5
votes
0answers
181 views
Resource-bounded variant of Kolmogorov complexity
Consider the variant of Kolmogorov complexity, where the program is only allowed to use a bounded amount of resources. This more closely resembles the practical situation, where decompression needs ...
5
votes
0answers
85 views
Computational depth and p-time hard instances
After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
4
votes
1answer
118 views
Relation between different “complexity theories” and complex systems theory
I know of at least 4 fundamentally different uses of the term "complexity theory":
the study of how hard a problem is to solve using some sort of computing machine (I am ignoring divisions within ...
4
votes
0answers
158 views
Alternative exponential definition of Kolmogorov complexity
In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined as
$$ K(x) = \mu e (\varphi_e(0) \simeq x) \, , $$
the smallest $e$ such ...
4
votes
0answers
166 views
Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?
at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim.
In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-...
4
votes
0answers
99 views
Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?
Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.
In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
4
votes
0answers
66 views
What is the shortest description of a universal computational structure that includes a meta-circular evaluator?
I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure....
4
votes
1answer
224 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 ...
3
votes
1answer
317 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 > ...
3
votes
1answer
250 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 ...
3
votes
1answer
196 views
Is joint Kolmogorov Complexity order invariant?
Due to the symmetry of information, it follows up to an additive constant that
K(X,Y) = K(Y,X)
Does this hold for more than two data objects as well?
