# Kolmogorov complexity applications in computational complexity

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

• 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. Aug 19 '10 at 0:29
• > Are you only looking for examples to problems that at first seem to have nothing to do with Kolmogorov complexity? Exactly so. Aug 19 '10 at 0:31

Lance Fortnow has written an article on this topic: Kolmogorov Complexity and Computational Complexity

You should also check out An Introduction to Kolmogorov Complexity and Its Applications 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 by Fortnow and Laplante).

And there are applications in communication complexity (e.g. Kolmogorov Complexity and Combinatorial Methods in Communication Complexity by Kaplan and Laplante).

• 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." Aug 19 '10 at 0:54
• I updated the post with some references that might be more in line with what you're looking for.
– Ian
Aug 19 '10 at 1:52

Just a few days ago Scott Aaronson used an argument based on Kolmogorov complexity to show the Equivalence of Sampling and Searching. 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.

This result 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".

• seems counterintuitive. does anyone know of other results relating bipartite graphs and regular graphs?
– vzn
Feb 21 '13 at 21:19

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, 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) and SICOMP 2006.

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.

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

"Lower bounds for randomized and quantum query complexity using Kolmogorov arguments" by Sophie Laplante and Frederic Magniez

(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. 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 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 (preprint)

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

• I would say that the latter paper applies computational complexity (namely, Nisan's pseudorandom generator) to resource-bounded Kolmogorov complexity, not vice versa. Oct 17 '10 at 12:19
• @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. Oct 17 '10 at 16:51

H. Buhrman, L. Fortnow, and S. Laplante. Resource-bounded Kolmogorov complexity revisited. SIAM Journal on Computing, 31(3):887-905, 2002. (journal, Lance's web page).

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

• I guess that the original Sipser's proof of "BPP is in Sigma_2" used Kolmogorov complexity. Aug 19 '10 at 0:50

One example is the following result that is described in survey by Bogdanov and Trevisan: there exists a distribution $D$ such that language is easy on-average with respect to $D$ iff it is worst-case-easy.

• There is a flaw in the proof in this version of survey, by the way. However, it can be fixed :) Aug 26 '10 at 5:24
• Care to elaborate? Aug 26 '10 at 5:45
• 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. Aug 26 '10 at 6:02
• Yes. I found a mistake, but I feel that I have more intuitive proof (with $1/n^{1 + \epsilon}$, though). Aug 26 '10 at 7:40

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

Do you mean something like this, ilyaraz?

http://arxiv.org/abs/1004.3993

• Yes, it seems encouraging. Aug 19 '10 at 1:51