<p>Lance Fortnow has written an article on this topic: <a href="http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf">Kolmogorov Complexity and Computational Complexity</a></p>

<p>You should also check out <a href="http://homepages.cwi.nl/~paulv/kolmogorov.html">An Introduction to Kolmogorov Complexity and Its Applications</a> by Li and Vitanyi, the definitive book on the subject.  In particular, chapter 6 "The Incompressibility Method" discusses a number of applications in complexity such as a Kolmogorov complexity proof of Hastad's switching lemma (from <a href="http://dx.doi.org/10.1006/inco.1995.1161">Circuit Lower Bounds à la Kolmogorov</a> by Fortnow and Laplante).</p>

<p>And there are applications in communication complexity (e.g. <a href="http://dx.doi.org/10.1007/978-3-642-02017-9_29">Kolmogorov Complexity and Combinatorial Methods in Communication Complexity</a> by Kaplan and Laplante).</p>

CC BY-SA 2.5
2010-08-19T00:49:24.023Z
Thank you. This article is very nice and useful, but what I want is applications without mentioning K-complexity in statements.
ilyaraz
CC BY-SA 2.5
2010-08-19T00:54:39.863Z
ilyaraz, although *most* of the results mentioned in this paper are implications rather than applications, you might consider the characterizations of complexity classes by Kolmogorov complexity as a weak form of "application."
Joshua Grochow
CC BY-SA 2.5
2010-08-19T01:52:05.753Z
I updated the post with some references that might be more in line with what you're looking for.
Ian
CC BY-SA 2.5
2010-08-19T00:41:23.430Z
2010-08-19T01:50:33.870Z
2010-08-19T01:50:33.870Z
Ian
<p>One excellent paper that I know of (in addition to those other excellent papers mentioned in other answers):</p>

<p>Juris Hartmanis, <a href="http://dx.doi.org/10.1109/SFCS.1983.21"><em>Generalized Kolmogorov Complexity and the Structure of Feasible Computations</em></a>, FOCS 1983.</p>

<p>The main thing I remember from that paper is a Kolmogorov complexity-based construction of an oracle separating P from NP.</p>

<p>Another paper that comes to mind is</p>

<p>Allender et al., <em>Power from Random Strings</em>, FOCS 2002 (<a href="http://eccc.uni-trier.de/report/2002/028/">ECCC version</a>) and <a href="http://dx.doi.org/10.1137/050628994">SICOMP 2006</a>.</p>

<p>If I recall, the latter paper separates polynomial-time Turing completeness from log-space many-one completeness in PSPACE, using Kolmogorov complexity arguments.  Of course, it does many other things, but I recall that separation being one application that is of independent interest outside of algorithmic information theory.</p>

CC BY-SA 2.5
2010-08-19T18:41:56.353Z
2010-08-24T11:38:13.907Z
2010-08-24T11:38:13.907Z
Dave Doty
<p><a href="http://portal.acm.org/citation.cfm?id=1238706.1238720">This result</a> by Alon et al. can be obtained by the means of Kolmogorov complexity.</p>

<p>"The set of edges E of every finite bipartite graph can be split into $\mathrm{poly}(\log |E|)$ subsets so that all the resulting bipartite graphs are almost regular".</p>

CC BY-SA 3.0
2013-02-21T21:19:02.543Z
seems counterintuitive. does anyone know of other results relating bipartite graphs and regular graphs?
vzn
CC BY-SA 2.5
2010-08-20T17:45:21.747Z
2010-08-20T17:45:21.747Z
ilyaraz
<p>Just a few days ago Scott Aaronson used an argument based on Kolmogorov complexity to show the <a href="http://eccc.hpi-web.de/report/2010/128/">Equivalence of Sampling and Searching</a>. Further he argues, that in his argument Kolmogorov complexity is used in an essential way, that is not just a short-cut for a counting argument.</p>

CC BY-SA 2.5
2010-08-19T05:28:09.293Z
2010-08-19T05:28:09.293Z
Martin Schwarz
<p>There's also a quantum lower bound technique that uses Kolmogorov complexity:</p>

<p>"<a href="http://arxiv.org/abs/quant-ph/0311189">Lower bounds for randomized and quantum query complexity using Kolmogorov arguments</a>" by Sophie Laplante and Frederic Magniez</p>

CC BY-SA 2.5
2010-09-08T02:13:59.257Z
2010-09-08T02:13:59.257Z
Robin Kothari
<p>(First, a jest.)  When faced with a difficult problem in computational complexity, there is always the joy of applied Kolmogorov complexity to lift one's spirits.  This is also known as <a href="http://en.wikipedia.org/wiki/Code_golf" rel="nofollow">code golf</a>.  For a range of small problems corresponding to strings $s$, one can explore the intrinsic complexity $K(s)$ competitively at <a href="http://codegolf.com/" rel="nofollow">http://codegolf.com/</a> or just for fun at <a href="http://golf.shinh.org/" rel="nofollow">http://golf.shinh.org/</a> (with 80 different languages at the latter site for which the <a href="http://en.wikipedia.org/wiki/Invariance_theorem" rel="nofollow">Invariance Theorem</a> constants need to be estimated).  <em>As with all undecidable functions, approach with caution.</em></p>

<p>(Now for the serious bit.)  Daniil Musatov has recently shown that naïve derandomization can provide reasonable constructions for objects that are usually shown to exist non-constructively via the probabilistic method.  I think this is likely to provide significant future applications of resource-bounded Kolmogorov complexity to computational complexity.</p>

<ul>
<li>Daniil Musatov,
<em>Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via ``Naive'' Derandomization</em>,
CSR 2011,
LNCS 6651,
64–76.
doi:<a href="http://dx.doi.org/10.1007/978-3-642-20712-9_6" rel="nofollow">10.1007/978-3-642-20712-9_6</a>
(<a href="http://arxiv.org/abs/1009.5108" rel="nofollow">preprint</a>)</li>
</ul>

<p>See also <a href="http://scholar.google.com/scholar?cites=3428921449285234718" rel="nofollow">papers citing this one</a>.</p>

<p>(Edit: linking to the later, published version.)</p>

CC BY-SA 2.5
2010-10-17T12:19:16.710Z
I would say that the latter paper applies computational complexity (namely, Nisan's pseudorandom generator) to resource-bounded Kolmogorov complexity, not vice versa.
ilyaraz
CC BY-SA 2.5
2010-10-17T16:51:28.623Z
@ilyaraz: That is an accurate summary.  I am stating that given the links in the one direction, it should be possible to make these applications work the other way too.
András Salamon
CC BY-SA 3.0
2010-08-21T00:14:51.977Z
2013-02-21T10:25:34.003Z
2013-02-21T10:25:34.003Z
András Salamon
<p>H. Buhrman, L. Fortnow, and S. Laplante. Resource-bounded Kolmogorov complexity revisited. SIAM Journal on Computing, 31(3):887-905, 2002. (<a href="http://dx.doi.org/10.1137/S009753979834388X">journal</a>, <a href="http://www.cs.uchicago.edu/~fortnow/papers/cd.pdf">Lance's web page</a>).</p>

<p>Includes applications of Kolmogorov complexity such as:</p>

<ul>
<li>A proof of Valiant-Vazirani</li>
<li>Satisfying assignments of Boolean formulae can be enumerated in time polynomial in the output size iff a unique assignment can be found quickly</li>
<li>A new proof that BPP is in Sigma_2 P</li>
<li>Several oracle constructions</li>
</ul>

<p>Some of the above were first proven in this paper, whereas others are simply new proofs of old theorems, using Kolmogorov complexity.</p>

<hr>

<p><a href="http://ftp.cs.rutgers.edu/pub/allender/chapter.pdf">Applications of time-bounded Kolmogorov complexity in complexity theory</a> is a nice survey by Eric Allender of other applications.  Although many of the results here are implications, some are true applications, such as the following:</p>

<ul>
<li>Cor 13: Relative to a generic oracle, there is no pseudorandom generator that is secure against P/poly adversaries.</li>
<li>Thm 16 [Allender and Gore, 1991]: There is an oracle relative to which all NE predicates are solvable in exponential time and E = Union_k \Sigma_k-TIME(n).</li>
</ul>

<p>Both proofs use Kolmogorov complexity significantly.</p>

CC BY-SA 2.5
2010-08-19T00:50:43.553Z
I guess that the original Sipser's proof of "BPP is in Sigma_2" used Kolmogorov complexity.
ilyaraz
CC BY-SA 2.5
2010-08-19T00:49:20.873Z
2010-08-19T01:05:57.813Z
2010-08-19T01:05:57.813Z
Joshua Grochow
<p>One example is the following result that is described in <a href="http://arxiv.org/abs/cs/0606037">survey by Bogdanov and Trevisan</a>:
there exists a distribution $D$ such that language is easy on-average with respect to $D$ iff it is worst-case-easy.</p>

CC BY-SA 2.5
2010-08-26T05:24:23.053Z
There is a flaw in the proof in this version of survey, by the way. However, it can be fixed :)
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-08-26T05:45:19.597Z
Care to elaborate?
ilyaraz
CC BY-SA 2.5
2010-08-26T06:02:12.317Z
By the way, I have a strange feeling that I can sharpen this proof: one could get rid of $1/n^3$ and put there any subconstant probability. I am curious where is a mistake.
ilyaraz
CC BY-SA 2.5
2010-08-26T07:40:40.690Z
Yes. I found a mistake, but I feel that I have more intuitive proof (with $1/n^{1 + \epsilon}$, though).
ilyaraz
CC BY-SA 2.5
2010-08-19T00:14:00.053Z
2010-08-19T00:14:00.053Z
ilyaraz
<p>Minimum Description Length uses Kolmogorov complexity (or approximations and generalizations thereof, due to undecidability) in information-theoretical learning and inference theory. Specifically, MDL is used to find explanations of data that naturally avoids overfitting.</p>

<p>Jorma Rissanen provides a good introduction to his concept: <a href="http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf">http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf</a></p>

CC BY-SA 2.5
2010-08-19T17:37:00.117Z
2010-08-19T17:37:00.117Z
Ross Snider
<p>Do you mean something like this, ilyaraz?</p>

<p><a href="http://arxiv.org/abs/1004.3993" rel="nofollow">http://arxiv.org/abs/1004.3993</a></p>

CC BY-SA 2.5
2010-08-19T01:51:13.353Z
Yes, it seems encouraging.
ilyaraz
CC BY-SA 2.5
2010-08-19T01:48:37.697Z
2010-08-19T01:48:37.697Z
Aaron Sterling
<p>Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$) It is easy to see that most of strings are random (there are not so many short programs).</p>

<p>Kolmogorov complexity theory and algorithmic information theory are quite developed nowadays. And there are several amusing examples of using Kolmogorov complexity in proofs of different theorems that do not contain anything about Kolmogorov complexity in their statements (<a href="http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html">constructive LLL</a>, <a href="http://en.wikipedia.org/wiki/Loomis-Whitney_inequality">Loomis-Whitney inequality</a> and so on).</p>

<p>Are there any nice applications of Kolmogorov complexity and algorithmic information theory in <strong>computational complexity and related fields</strong>? I feel that there should be results that use Kolmogorov complexity as a straightforward replacement of simple counting arguments. This is, of course, not that interesting.</p>

CC BY-SA 2.5
2010-08-19T00:29:12.207Z
Are you only looking for examples to problems that at first seem to have nothing to do with Kolmogorov complexity?  There are lots of results on the computational complexity of various sets defined in terms of Kolmogorov complexity (most notably the set of Kolmogorov-random strings), and also plenty of results relating resource-bounded Kolmogorov complexity to standard complexity things (like P vs NP, factoring, etc).  But I'm not sure if the latter are what you are looking for or not.
Joshua Grochow
CC BY-SA 2.5
2010-08-19T00:31:31.407Z
> Are you only looking for examples to problems that at first seem to have nothing to do with Kolmogorov complexity?

Exactly so.
ilyaraz
<cc.complexity-theory><big-list><co.combinatorics><it.information-theory>
Kolmogorov complexity applications in computational complexity
ilyaraz
# Kolmogorov complexity applications in computational complexity

(Asked by: username_0 on 2010-08-19)

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$) It is easy to see that most of strings are random (there are not so many short programs).

Kolmogorov complexity theory and algorithmic information theory are quite developed nowadays. And there are several amusing examples of using Kolmogorov complexity in proofs of different theorems that do not contain anything about Kolmogorov complexity in their statements ([constructive LLL](http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html), [Loomis-Whitney inequality](http://en.wikipedia.org/wiki/Loomis-Whitney_inequality) and so on).

Are there any nice applications of Kolmogorov complexity and algorithmic information theory in **computational complexity and related fields**? I feel that there should be results that use Kolmogorov complexity as a straightforward replacement of simple counting arguments. This is, of course, not that interesting.

**Tags:** cc.complexity-theory, big-list, co.combinatorics, it.information-theory

> **Comments:**
> **username_1**: Are you only looking for examples to problems that at first seem to have nothing to do with Kolmogorov complexity?  There are lots of results on the computational complexity of various sets defined in terms of Kolmogorov complexity (most notably the set of Kolmogorov-random strings), and also plenty of results relating resource-bounded Kolmogorov complexity to standard complexity things (like P vs NP, factoring, etc).  But I'm not sure if the latter are what you are looking for or not.  
> **username_0**: > Are you only looking for examples to problems that at first seem to have nothing to do with Kolmogorov complexity?  Exactly so.  

---

## 10 answers

### Answer by username_2 on 2010-08-19. Score: 18

Lance Fortnow has written an article on this topic: [Kolmogorov Complexity and Computational Complexity](http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf)

You should also check out [An Introduction to Kolmogorov Complexity and Its Applications](http://homepages.cwi.nl/~paulv/kolmogorov.html) by Li and Vitanyi, the definitive book on the subject. In particular, chapter 6 "The Incompressibility Method" discusses a number of applications in complexity such as a Kolmogorov complexity proof of Hastad's switching lemma (from [Circuit Lower Bounds à la Kolmogorov](http://dx.doi.org/10.1006/inco.1995.1161) by Fortnow and Laplante).

And there are applications in communication complexity (e.g. [Kolmogorov Complexity and Combinatorial Methods in Communication Complexity](http://dx.doi.org/10.1007/978-3-642-02017-9_29) by Kaplan and Laplante).

> **Comments:**
> **username_0**: Thank you. This article is very nice and useful, but what I want is applications without mentioning K-complexity in statements.  
> **username_1**: username_0, although *most* of the results mentioned in this paper are implications rather than applications, you might consider the characterizations of complexity classes by Kolmogorov complexity as a weak form of "application."  
> **username_2**: I updated the post with some references that might be more in line with what you're looking for.  

---

### Answer by username_5 on 2010-08-19. Score: 15

Just a few days ago Scott Aaronson used an argument based on Kolmogorov complexity to show the [Equivalence of Sampling and Searching](http://eccc.hpi-web.de/report/2010/128/). Further he argues, that in his argument Kolmogorov complexity is used in an essential way, that is not just a short-cut for a counting argument.


---

### Answer by username_3 on 2010-08-19. Score: 11

One excellent paper that I know of (in addition to those other excellent papers mentioned in other answers):

Juris Hartmanis, [*Generalized Kolmogorov Complexity and the Structure of Feasible Computations*](http://dx.doi.org/10.1109/SFCS.1983.21), FOCS 1983.

The main thing I remember from that paper is a Kolmogorov complexity-based construction of an oracle separating P from NP.

Another paper that comes to mind is

Allender et al., *Power from Random Strings*, FOCS 2002 ([ECCC version](http://eccc.uni-trier.de/report/2002/028/)) and [SICOMP 2006](http://dx.doi.org/10.1137/050628994).

If I recall, the latter paper separates polynomial-time Turing completeness from log-space many-one completeness in PSPACE, using Kolmogorov complexity arguments. Of course, it does many other things, but I recall that separation being one application that is of independent interest outside of algorithmic information theory.


---

### Answer by username_0 on 2010-08-20. Score: 11

[This result](http://portal.acm.org/citation.cfm?id=1238706.1238720) by Alon et al. can be obtained by the means of Kolmogorov complexity.

"The set of edges E of every finite bipartite graph can be split into $\mathrm{poly}(\log |E|)$ subsets so that all the resulting bipartite graphs are almost regular".

> **Comments:**
> **username_4**: seems counterintuitive. does anyone know of other results relating bipartite graphs and regular graphs?  

---

### Answer by username_6 on 2010-09-08. Score: 9

There's also a quantum lower bound technique that uses Kolmogorov complexity:

"[Lower bounds for randomized and quantum query complexity using Kolmogorov arguments](http://arxiv.org/abs/quant-ph/0311189)" by Sophie Laplante and Frederic Magniez


---

### Answer by username_7 on 2010-08-21. Score: 9

(First, a jest.) When faced with a difficult problem in computational complexity, there is always the joy of applied Kolmogorov complexity to lift one's spirits. This is also known as [code golf](http://en.wikipedia.org/wiki/Code_golf). For a range of small problems corresponding to strings $s$, one can explore the intrinsic complexity $K(s)$ competitively at <http://codegolf.com/> or just for fun at <http://golf.shinh.org/> (with 80 different languages at the latter site for which the [Invariance Theorem](http://en.wikipedia.org/wiki/Invariance_theorem) constants need to be estimated). *As with all undecidable functions, approach with caution.*

(Now for the serious bit.) Daniil Musatov has recently shown that naïve derandomization can provide reasonable constructions for objects that are usually shown to exist non-constructively via the probabilistic method. I think this is likely to provide significant future applications of resource-bounded Kolmogorov complexity to computational complexity.

* Daniil Musatov,
  *Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via ``Naive'' Derandomization*,
  CSR 2011,
  LNCS 6651,
  64–76.
  doi:[10.1007/978-3-642-20712-9\_6](http://dx.doi.org/10.1007/978-3-642-20712-9_6)
  ([preprint](http://arxiv.org/abs/1009.5108))

See also [papers citing this one](http://scholar.google.com/scholar?cites=3428921449285234718).

(Edit: linking to the later, published version.)

> **Comments:**
> **username_0**: I would say that the latter paper applies computational complexity (namely, Nisan's pseudorandom generator) to resource-bounded Kolmogorov complexity, not vice versa.  
> **username_7**: @username_0: That is an accurate summary.  I am stating that given the links in the one direction, it should be possible to make these applications work the other way too.  

---

### Answer by username_1 on 2010-08-19. Score: 8

H. Buhrman, L. Fortnow, and S. Laplante. Resource-bounded Kolmogorov complexity revisited. SIAM Journal on Computing, 31(3):887-905, 2002. ([journal](http://dx.doi.org/10.1137/S009753979834388X), [Lance's web page](http://www.cs.uchicago.edu/~fortnow/papers/cd.pdf)).

Includes applications of Kolmogorov complexity such as:

* A proof of Valiant-Vazirani
* Satisfying assignments of Boolean formulae can be enumerated in time polynomial in the output size iff a unique assignment can be found quickly
* A new proof that BPP is in Sigma\_2 P
* Several oracle constructions

Some of the above were first proven in this paper, whereas others are simply new proofs of old theorems, using Kolmogorov complexity.

---

[Applications of time-bounded Kolmogorov complexity in complexity theory](http://ftp.cs.rutgers.edu/pub/allender/chapter.pdf) is a nice survey by Eric Allender of other applications. Although many of the results here are implications, some are true applications, such as the following:

* Cor 13: Relative to a generic oracle, there is no pseudorandom generator that is secure against P/poly adversaries.
* Thm 16 [Allender and Gore, 1991]: There is an oracle relative to which all NE predicates are solvable in exponential time and E = Union\_k \Sigma\_k-TIME(n).

Both proofs use Kolmogorov complexity significantly.

> **Comments:**
> **username_0**: I guess that the original Sipser's proof of "BPP is in Sigma_2" used Kolmogorov complexity.  

---

### Answer by username_0 on 2010-08-19. Score: 6

One example is the following result that is described in [survey by Bogdanov and Trevisan](http://arxiv.org/abs/cs/0606037):
there exists a distribution $D$ such that language is easy on-average with respect to $D$ iff it is worst-case-easy.

> **Comments:**
> **username_8**: There is a flaw in the proof in this version of survey, by the way. However, it can be fixed :)  
> **username_0**: Care to elaborate?  
> **username_0**: By the way, I have a strange feeling that I can sharpen this proof: one could get rid of $1/n^3$ and put there any subconstant probability. I am curious where is a mistake.  
> **username_0**: Yes. I found a mistake, but I feel that I have more intuitive proof (with $1/n^{1 + \epsilon}$, though).  

---

### Answer by username_9 on 2010-08-19. Score: 5

Minimum Description Length uses Kolmogorov complexity (or approximations and generalizations thereof, due to undecidability) in information-theoretical learning and inference theory. Specifically, MDL is used to find explanations of data that naturally avoids overfitting.

Jorma Rissanen provides a good introduction to his concept: <http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf>


---

### Answer by username_10 on 2010-08-19. Score: 3

Do you mean something like this, username_0?

<http://arxiv.org/abs/1004.3993>

> **Comments:**
> **username_0**: Yes, it seems encouraging.  

---

