# Computational Complexity

### Thursday, May 01, 2003

History's Loss/Mathematics' Gain

Some excitement at Schloss Dagstuhl this week. Localized high winds tore the metal plating off the roof of much of the new building Wednesday evening. Much of that roof sits in the courtyard--quite a sight. The good news is no one was injured and property damage, besides the roof, was minimal. A few of us had to switch rooms but the workshop goes on.

Let me finish off this centennial week with a story of Kolmogorov that I have heard from different sources so some variation of this story is likely true. Kolmogorov initially wanted to be an historian. He looked at the question as to whether taxes in Russia in the middle-ages were collected at the house level or at the village level. He analyzed tax data and showed that that data had a much simpler description if taxes were collected at the village level. (You can see the seeds of Kolmogorov complexity here). He presented these results to the history faculty to great applause. Asking them whether he could publish such a paper he was told, "You only have one proof. You cannot publish in a history journal without at least two more proofs of your hypothesis." And so Kolmogorov left history for a field where one proof suffices.

### Wednesday, April 30, 2003

The Power of Random Strings

Let R be the set of random strings, the x such that C(x)≥|x|. There are various theorems that many such x must exist at every length. What is the power of R?

R is co-r.e. as one can enumerate small programs to generate the strings x such that C(x)<|x|. One can also reduce the halting problem to R: Suppose we want to know whether a program p halts on blank tape. Let n=|p|. Let t be the number of steps to enumerate all of the strings in R of length 2n. We know when we have enumerated them all by using R. Then if p halts it will halt within t steps. Otherwise let s>t be the number of steps p needs to halt. We can run the enumeration of strings in R of length 2n for s steps. Let x be the lexicographically least string of length 2n not enumerated. We have C(x)≤|p|+O(1) since we need only p to describe this process. But since |p|<2n=|x| this contradicts the fact that we had enumerated all the nonrandom strings.

In this workshop Eric Allender talked about his work with various colleagues looking at what one can get with polynomial-time reductions to random strings. The reduction time above is not bounded by any recursive function. For example they can show any language in PSPACE polynomial-time reduces to R and any language in EXP reduces to R via polynomial-size circuits, as well as many results on different notions of random strings. They use various complexity tools like pseudorandom generators and interactive proof systems in their proofs.

### Tuesday, April 29, 2003

More on Kolmogorov Complexity

There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but you might find it at the bottom of Sophie Laplante's web page). Reading the cartoon you might find it funny because not all strings seem equally random even if they are equally likely. Kolmogorov formalized this idea by measuring the randomness of a string x, denoted C(x), by the smallest program that generates x.

At this Dagstuhl workshop there are many talk on a number of variations of Kolmogorov complexity. John Tromp had a nice presentation on the basic notion. He showed, among other things, that for any x you can find a constant length y such that C(xy)>C(x). This seems obvious but it is pretty tricky tor prove. Tromp's proof works by defining a new C-based measure on strings and using that to show that any string x has a small number of programs generating x that have length close to C(x) and using that fact to get his result. He doesn't have a write-up yet, but I'll keep a lookout for it.

### Sunday, April 27, 2003

Kolmogorov Centennial

Andrei Kolmogorov was born exactly hundred years ago last Friday the 25th. Kolmogorov made major contributions to "every mathematical area except number theory" as many a Russian have put it. He has directly affected my research through his algorithmic study of randomness, an area we now call Kolmogorov complexity.

To celebrate the centennial, I'm back in Dagstuhl for a workshop on Kolmogorov complexity after a brief stop in Heidelberg. Most of the best researchers in the area are here including many Russians. It should be an exciting week all around and during the week I will post some of the interesting work that I hear about.

For a background on Kolmogorov complexity, here are some lecture notes from a short course I gave. For an in-depth study, I cannot recommend enough the Kolmogorov Complexity book of Li and Vitanyi.