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.
91
questions
1
vote
0
answers
47
views
Relation Between Different Definitions of Information Distance
I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
2
votes
0
answers
69
views
Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs
$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...
- 187
6
votes
1
answer
228
views
Fast algorithms for time bounded Kolmogorov complexity
For a universal Turing machine $U$, the time bounded Kolmogorov complexity of a string $x$ is silmilar to the usual Kolmogorov complexity but limited to programs $p$ running in time at most $t(|x|)$:
$...
- 187
1
vote
1
answer
106
views
Clarification sought re Li & Vitanyi's Proof of Godel Incompleteness in Formal System F
(Cross-posted from Computer Science due to lack of response after 1 week)
From An Introduction to Kolmogorov Complexity and Its Applications, Li & Vitany, 4th Ed. Example 1.1.1.
As you might guess,...
- 113
1
vote
0
answers
122
views
How to measure the weirdness of algorithms?
Let $M$ is a polynomial $k$-tape Turing machine and $C^t(x)$ is a time-bounded Kolmogorov complexity.
Let $str_M(x)$ be a string of the following form:
$$str_M(x)=w_1^1\# w_2^1 \# ... \# w_{m}^1 ■ w_1^...
- 49
2
votes
0
answers
101
views
Online *detailed* tutorials about Komogorov Complexity
I'm a private math tutor who also tutors some theoretical CS. Last semester I had a student who needed tutoring in Kolmogorov Complexity. I told her that I only know about Kolmogorov Complexity, but ...
5
votes
1
answer
234
views
Upper bound on the expected number of correct bits via a "lossy compression"
Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
2
votes
0
answers
53
views
program search with optimization methods for (resource bounded) Kolmogorov complexity
Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
- 31
1
vote
0
answers
55
views
sophistication or logical depth to detect intelligent extra-terrestrial species
From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
- 31
3
votes
1
answer
149
views
An invariance theorem for algorithmically random data in statistical learning
Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of ...
- 311
7
votes
1
answer
200
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 ...
- 285
3
votes
1
answer
126
views
how to define "correlation" between languages?
How does one define the concept of correlation between languages?
Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this ...
- 301
4
votes
0
answers
171
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 ...
- 41
1
vote
0
answers
71
views
Reference request on using Kolmogorov complexity to measure the simplicity of models
Have there been any serious attempts to use the notion of Kolmogorov complexity to measure the simplicity of models outside of theoretical CS? I mean models in the english sense - any logical set of ...
1
vote
0
answers
95
views
Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?
Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
- 41
5
votes
1
answer
240
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 ...
- 583
1
vote
0
answers
73
views
existence & characterization of "kolmogorov efficient" programs
$\newcommand{\Prog}{\operatorname{Prog}}\newcommand{\kol}{\operatorname{kol}}$
Disclaimer: I do not have a formal background in algorithmic complexity theory so apologies if I use non-standard ...
- 111
1
vote
0
answers
234
views
Fast algorithms for evaluating functions with high Kolmogorov complexity
Motivation:
I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I ...
- 311
3
votes
1
answer
225
views
Kolmogorov Complexity of the composition of two computable functions
Let's suppose we encode two computable functions $f$ and $g$ as binary strings so $f,g \in \{0,1\}^*$. What I am curious about is whether we can find good upper and lower bounds for:
\begin{equation}...
- 311
1
vote
1
answer
318
views
Prime factorisation of decidable problems
Disclaimer: I am not a theoretical computer scientist.
The set of decidable problems $\mathbb{D}$ is countable so $\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$ and this led me to the ...
- 311
1
vote
0
answers
83
views
A question on the Kolmogorov Complexity of Human I/O behaviour
Note: From my Twitter poll I managed to get feedback from AI researchers and neuroscientists so far and I think it would be interesting to get input from theoretical computer scientists on this ...
- 311
2
votes
0
answers
72
views
How to improve this pseudorandom generator?
Let $f$ be a Boolean function and $\varepsilon > 0$.
There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property.
Let $T$ be a set and $p(n)$...
- 1,973
6
votes
1
answer
374
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 ...
- 163
3
votes
1
answer
101
views
Commonality of minimal Kolmogorov structure functions
A typical $B$ is difficult to define precisely. Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s. However, the concept can be clarified ...
- 203
6
votes
1
answer
292
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 ...
- 203
8
votes
0
answers
180
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 ...
- 181
4
votes
1
answer
151
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 ...
- 433
1
vote
1
answer
97
views
What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?
If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $...
- 1,572
2
votes
1
answer
510
views
Does there exist an ontology for algorithms?
It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of ...
- 309
6
votes
1
answer
435
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 ...
- 471
2
votes
1
answer
116
views
Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity
Let $$f(c)=\min_{x \ge c} K(x)$$ where $K(x)$ is the kolmogorov complexity of $x$. Since $K(x)$ is always a natural number, there will always be a minimum. My question is, what is the growth rate of $...
- 471
2
votes
0
answers
89
views
What's the distribution of the Kolmogorov complexity of the elements in the set of bitstrings of length n?
take e.g. all possible bitstrings of length n=10,000. there are 2^10,000 of them. imagine that for each of those strings we knew the length of the shortest program that could produce the string. what ...
- 29
1
vote
0
answers
66
views
Parametrically-relaxed Kolmogorov complexity
Consider the following problem:
Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation.
Output: The encoding of some kind of automaton (say, a Turing machine) which ...
- 173
8
votes
1
answer
347
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 ...
- 516
4
votes
0
answers
195
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-...
- 41
3
votes
0
answers
263
views
A sequence wherein the Kolmogorov complexity of the terms does not increase
I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that :
It can be proved in some axiomtic system $S$ that: $\...
- 405
6
votes
1
answer
450
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) := ...
- 2,037
3
votes
1
answer
153
views
How to extend Solomonoff Induction to continuous domain
Informally speaking, Solomonoff Induction provides an Bayesian optimal way to predict the next symbol from observed symbol sequences $S_1S_2S_3...S_n$ where each $S_i$ belongs to a finite symbol set $\...
- 131
18
votes
1
answer
966
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. -...
- 36.9k
3
votes
1
answer
242
views
Compression algorithms for low-complexity strings?
Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there ...
- 35
6
votes
1
answer
301
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^{...
- 111
7
votes
1
answer
695
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)....
- 1,973
4
votes
0
answers
107
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 ...
- 653
0
votes
0
answers
158
views
Questions about the definition of the Quantum Turing Machine
I am trying to have a better understanding of the definition of the Quantum Turing Machine.
My questions:
If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
- 653
5
votes
0
answers
88
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 ...
5
votes
0
answers
94
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....
- 314
0
votes
3
answers
605
views
Fastest Turing Machine
Recently I have been reading about Kolmogorov Complexity.
As such I started thinking about the "fastest turing machine".
In particular I am not interested in finding such a machine, I am only ...
user35803
1
vote
1
answer
110
views
How to quantify the complexity of vectors whose components are real numbers?
I started to study Kolmogorov complexity today, and this question came to mind. Is there any way to use LZW to do this? I'm looking for a guidance to my studies
- 13
1
vote
1
answer
124
views
"Checking equality for Kolmogorov complexity of two sequences" is computable?
It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not:
"Given $x$ and $y$ as two sequences, ...
- 111
-3
votes
1
answer
400
views
Are nearly all natural numbers compressible? [closed]
There are numerous proofs that most strings are incompressible. I am interested in strings that represent natural numbers. Assume the Kolmogorov complexity of a natural number, $K(n)$, is the smallest ...
- 549