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

95 questions
Filter by
Sorted by
Tagged with
154 views

### A potentially novel complexity measure for sets of strings

Inspired partly by Scott Aaronson's post about the first law of complexodynamics, I've been thinking lately about how to quantify the "interesting" or "structured" complexity of a ...
189 views

### Is $K^t$ complexity closed under composition

Call an increasing function $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ reasonable if $\forall c \in \mathbb{N}, \exists_\infty n, c K^{2n}(n) \leq \alpha (n)$. Where $K^t$ is the time bounded ...
• 309
37 views

### Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size

Suppose we have a lossless compression algorithm A, which compresses a string of length $n$.The symbols in the string are chosen uniformly at random from an alphabet with cardinality $p$. Different ...
195 views

### Does every computable function have infinitely many "non-padded" representations?

It's well-known that every computable function has infinitely many representations (when they're expressed via recursive functions, or programs, etc.). I'm trying to understand whether there are ...
• 151
1 vote
126 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.&...
74 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
303 views

• 131
1k 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. -...
• 37.9k
251 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
306 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
713 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)....
• 2,013
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 ...
• 661
1 vote
161 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 ...
• 661
89 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 ...
99 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....
• 312