<p>You can use LZW or other standard compression methods to approximate the Kolmogorov complexity. In some real-world cases this works well. However, it is dangerous, as it can also be a pretty bad approximation to the true Kolmogorov complexity, viz. <a href="http://bactra.org/notebooks/cep-gzip.html" rel="nofollow">http://bactra.org/notebooks/cep-gzip.html</a>.</p>

<p>Another option is to seek the smallest Boolean circuit that outputs a given string. This problem appears to be hard*, but (a) isn't uncomputable like $K(x)$, and (b) doesn't suffer from the potentially erroneous measure given by gzip etc. (since circuits are a standard non-uniform, universal model of computation).</p>

<p>*[<strong>Update</strong>: It's actually essentially the Minimum Circuit Size Problem, which is looking like it's not $\mathsf{NP}$-hard, but it's still quite hard.]</p>

CC BY-SA 3.0
2015-09-22T16:24:53.740Z
@RickyDemer: Whoops, you're right. It's essentially MCSP, which isn't known to be - and perhaps is even thought not to be - NP-hard. But it's still a pretty hard problem (at least as hard as all of SZK, under randomized reductions).
Joshua Grochow
CC BY-SA 3.0
2015-09-21T21:00:30.757Z
2015-09-22T16:23:58.710Z
2015-09-22T16:23:58.710Z
Joshua Grochow
<p>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</p>

<cc.complexity-theory><kolmogorov-complexity>
How to quantify the complexity of vectors whose components are real numbers?
daemon
# How to quantify the complexity of vectors whose components are real numbers?

(Asked by: username_0 on 2015-09-21)

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

**Tags:** cc.complexity-theory, kolmogorov-complexity

---

## 1 answers

### Answer by username_1 on 2015-09-21. Score: 4 | Accepted answer

You can use LZW or other standard compression methods to approximate the Kolmogorov complexity. In some real-world cases this works well. However, it is dangerous, as it can also be a pretty bad approximation to the true Kolmogorov complexity, viz. <http://bactra.org/notebooks/cep-gzip.html>.

Another option is to seek the smallest Boolean circuit that outputs a given string. This problem appears to be hard\*, but (a) isn't uncomputable like $K(x)$, and (b) doesn't suffer from the potentially erroneous measure given by gzip etc. (since circuits are a standard non-uniform, universal model of computation).

\*[**Update**: It's actually essentially the Minimum Circuit Size Problem, which is looking like it's not $\mathsf{NP}$-hard, but it's still quite hard.]

> **Comments:**
> **username_1**: @RickyDemer: Whoops, you're right. It's essentially MCSP, which isn't known to be - and perhaps is even thought not to be - NP-hard. But it's still a pretty hard problem (at least as hard as all of SZK, under randomized reductions).  

---

