# 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.

80 questions
Filter by
Sorted by
Tagged with
106 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 ...
154 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 ...
64 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 ...
54 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 '...
143 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 ...
71 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 ...
188 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 . To be more precise, I ...
147 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}...
224 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 ...
76 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 ...
56 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)$...
312 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 ...
89 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 ...
242 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 ...
151 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 ...
116 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 ...
76 views

84 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 ...
56 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 ...
178 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 ...
159 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-...