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

86 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
868 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 ...
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 ...
846 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. -...
1k 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 ...
495 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 ...
413 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)...
487 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 ...
648 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. ...
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 ...
259 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 ...
662 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}$ ...
361 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 ...
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, ...
212 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$...
1k 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 ...
161 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 ...
278 views

164 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 ...
144 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 ...
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 ...
189 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 ...
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" ...
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-...
162 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 ...
204 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 ...
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 ...
126 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 ...
164 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 ...
180 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-...
101 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 ...
67 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....
231 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 ...
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 > ...