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.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
146 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 ...
6
votes
0answers
153 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
141 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
34 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
158 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
0answers
158 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
0answers
141 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
98 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
1answer
215 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
0answers
253 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: $\...
3
votes
0answers
64 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....
3
votes
0answers
117 views

What is the problem of finding a largest subset of smallest Kolmogorov complexity?

What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting ...
2
votes
0answers
169 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 ...
2
votes
0answers
55 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 $...
2
votes
0answers
83 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 ...
2
votes
0answers
71 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 $\...
2
votes
0answers
60 views

Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: http://hal.inria.fr/docs/00/74/77/09/PDF/NonRedundantGeneration-TCS-2010....
1
vote
0answers
73 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 ...
1
vote
0answers
52 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 ...
1
vote
0answers
79 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 ...
0
votes
0answers
150 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 ...
-1
votes
0answers
50 views

Is checking time-bounded Kolmogorov complexity of a string claiming to be the shortest string in a certain amount of time EXPTIME?

Time bounded Kolmogorov complexity is the smallest amount of data that can output a given piece of data within a given amount of time. For this example, Kolmogorov complexity is defined as being able ...