46
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Aug 19, 2010 at 0:29
  • 1
    $\begingroup$ > Are you only looking for examples to problems that at first seem to have nothing to do with Kolmogorov complexity? Exactly so. $\endgroup$
    – ilyaraz
    Aug 19, 2010 at 0:31

10 Answers 10

Reset to default
18
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you. This article is very nice and useful, but what I want is applications without mentioning K-complexity in statements. $\endgroup$
    – ilyaraz
    Aug 19, 2010 at 0:49
  • 1
    $\begingroup$ 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." $\endgroup$
    – Joshua Grochow
    Aug 19, 2010 at 0:54
  • $\begingroup$ I updated the post with some references that might be more in line with what you're looking for. $\endgroup$
    – Ian
    Aug 19, 2010 at 1:52
15
$\begingroup$

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.

Improve this answer
$\endgroup$
11
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ seems counterintuitive. does anyone know of other results relating bipartite graphs and regular graphs? $\endgroup$
    – vzn
    Feb 21, 2013 at 21:19
11
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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

Improve this answer
$\endgroup$
9
$\begingroup$

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

See also papers citing this one.

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I would say that the latter paper applies computational complexity (namely, Nisan's pseudorandom generator) to resource-bounded Kolmogorov complexity, not vice versa. $\endgroup$
    – ilyaraz
    Oct 17, 2010 at 12:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – András Salamon
    Oct 17, 2010 at 16:51
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I guess that the original Sipser's proof of "BPP is in Sigma_2" used Kolmogorov complexity. $\endgroup$
    – ilyaraz
    Aug 19, 2010 at 0:50
6
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
3
$\begingroup$

Do you mean something like this, ilyaraz?

http://arxiv.org/abs/1004.3993

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, it seems encouraging. $\endgroup$
    – ilyaraz
    Aug 19, 2010 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.