How Powerful are Random Strings?

Eric Allender and Luke Friedman and William Gasarch have written a paper that shows why it is good for a student to be exposed to experts in various areas. Luke is Eric’s student. Both Eric and Bill can individually be called “experts in various areas,” but here the symmetric difference of their area clouds seems to have been more important than their intersection. Eric is particularly known as an expert in Kolmogorov complexity, and has led a longstanding project to relate various versions of it to computational randomness. Bill has training in logic and recursion theory, and is adept at proof techniques that work by meeting—and sometimes injuring—infinitely many requirements in some priority order. The paper features a new result in Kolmogorov complexity obtained by meeting such requirements.

In such cases, what is a student to do? I (Ken) say learn the symmetric difference—then you don’t have to worry about just keeping up with either advisor.

Bill has a paper published in the logic journal, the Journal of Symbolic Logic, which I (Dick) find extremely impressive. The paper is also impressive—it is joint with Stephen Fenner and Brian Postow, the latter when a student of the late and much-loved Carl Smith. (I, Ken, also have a paper with Smith and Postow, one well outside my areas.)

Bill of course also co-authors the famous blog Computational Complexity with Lance Fortnow. Blogging promotes his research by exposing him more to other areas, such as Eric’s. Eric has not written for any blogs—not even a guest post can we find. Non-blogging promotes his research by giving him more time to write papers that involve other areas, such as Bill’s.

Today I (Dick) wish to talk about their paper itself, which will appear at ICALP 2011. It has the interesting, but general, title, “Limits on the Computational Power of Random Strings.” While its title is general I believe it is a terrific, important, and potentially seminal paper. As usual see the paper for the full statements of the theorems, and for all the details. What I want to do is just give a flavor of their results—while Ken wants to take a larger view on the problems they are trying to solve. Hopefully the symmetric difference of what we brought to this post will still be clear enough to motivate you to read their paper carefully, and even write the next paper.

Random Strings

Recall the set of random strings comprises those strings that have no shorter description than just . This elides a technical issue—but essentially it is correct. A string can be described in many ways, and it is in if there is not a much better way to describe other than presenting the string itself. This notion was created in 1965 in a short note by the great Andrei Kolmogorov. Bruno Durand and Alexander Zvonkin in an article on this notion said:

As was common with him, Kolmogorov, published, in 1965, a short note that started a new line of research.

Very impressive. Perhaps we should all publish more short notes—alas probably only someone like Kolmogorov can create whole areas this way.

There now is a large body of results on Kolmogorov random strings. They have been used in many areas of theory, including lower bounds, proof theory, and protocols. There are two basic results from this area. First, a string chosen uniformly at random is likely to be in . Second, determining whether a string is in is uncomputable. The former follows from a simple, almost trivial, counting argument; the latter follows essentially from the undecidability of the halting problem.

The Main Problem

Bill, Eric, and Luke study the set of Kolmogorov random strings from this point of view: How powerful is the ability to access an oracle with questions of the form ?

Previously results were known of the form:

The classes are , , , among others. The left-hand sides were always computable complexity classes, but the right-hand sides were not obviously even computable. This follows since the right-hand side uses access to , and is of course well known to be uncomputable. Three prior such results by Eric and/or his frequent co-authors (not Bill—indeed this is their first collaboration), using to mean the class of languages that polynomial-time truth-table reduce to , are:

Since the right-hand sides have power beyond what is computable, however, are these inclusions really meaningful? What one would like are equalities, giving new characterizations of these classes, which would quantify the algorithmic power of the random strings.

A simple idea is to intersect the right-hand sides of these inclusions with the class of decidable sets. As one might expect, this merely caps the problem at itself: for any time function there is a set that reduces to .

However, they observed that the manner of building such sets always exploited a technical feature of how is defined, namely the choice of a particular universal Turing machine. This means that what was previously seen as an “academic” issue was mattering concretely to complexity classes. Well, let’s approach it as an academic issue, along lines of today’s “postmodern” liberal arts culture.

The “Postmodern Problem” of Information Theory

As described at the outset by Wikipedia, Postmodernism is characterized by the revelation that apparent absolutes are based on relative constructs, especially regarding the language by which they are conveyed.

Now if there is one quantity in Computer Science that we feel should be absolute, surely it is the measure of information. After all, in many human languages, computer science itself is called some word form of Informatics. In computational complexity theory, we have by-and-large agreed that the multitape Turing machine is the model that provides the “standard meter.” The maximum number of steps taken by a program on inputs of a given length is a unique way to quantify the time complexity of the program. All Kolmogorov-complexity measures of information, however, are relative to a particular choice of a universal Turing machine by which to define the measure:

It is ironic that the machine model is absolute for time complexity, but the machines are themselves the relative element for . In normative terms, one might expect a need to choose the best , but the theory doesn’t do this. Instead it shows that the choice affects only up to a fixed additive constant depending only on . Results in the theory either work the same for any particular , or are asymptotic in a way that the constant doesn’t matter.

In this recent contest to find short universal Turing machines, the first concrete items under “Goals and Motivations” involve Kolmogorov complexity, next to a photo of Kolmogorov himself. They reference John Tromp’s “utterly simple computer model” and this paper by Jean-Paul Delahaye and Hector Zenil trying to find a “stable” definition. Delahaye and Zenil remark that the range of values of arising from natural is “so large that in practice it plays a major role” in concretely quantifying . One feels that how much information a string contains should be independent of choices within the machine model.

For Eric, Luke, and Bill this is a problem because they don’t really have a single set . Instead what the theory gives them is a multitude of sets

The particular point is that the constant which is hidden in this definition can matter to infinitely many strings. This is not just a finite difference in the sets . The program may have a special feature exploited to give infinitely many strings a description less than , though greater than . The difference of having or not having infinitely many strings can affect even asymptotic complexity results. They found that this was causing the power problem even after intersecting with .

Here we note the technical issue elided above. Given a seed string for , how do we know whether is describing itself or commands to produce some other string? We can disambiguate by adding a leading or trailing quote symbol, like ' or quote in Lisp. Adding a trailing quote symbol produces a prefix code, since ' is illegal for all non-empty strings . This is handled more naturally without introducing a quote symbol by demanding that the domain of be a prefix code to begin with. Thus is technically defined by restricting to universal machines that have this property.

Their Solution and New Results

Looking for a “best” would not solve the problem. Every individual —even with the prefix-code restriction—still makes arbitrarily complex decidable sets reduce to , even under the strongly restrictive notion of disjunctive truth-table () reducibility. Instead they take all the ‘s by the horns by intersecting over them.

One might think to define with the idea that truly random strings aren’t helped by any . However this set is empty—every string has a that embeds it and outputs it from a short command. The distinctive insight, which Eric and company actually had from an earlier paper, is to intersect the reduction classes. This gave a characterization of via the reducibility:

This is accomplished by turning the problem on its head: for every decidable language not in , we can find a such that does not poly-time -reduce to . This excludes from the intersection, leaving just on the right-hand side. This already is very neat, an upside-down kind of diagonalization where you build a machine rather than defeat one. But how to diagonalize against the stronger reductions, even against oracle machines?

Enter Bill and inter Luke, in-between. Here is one sentence that shows the kind of intellectual proof complexity needed:

We break this requirement up into an infinite number of requirements.

Then each new requirement gives rise to a game, which is another tool of logicians. The games body-check the requirements in priority order and sometimes injure them—since Atlanta is about to lose its ice hockey team, this will have to substitute. As before, please see the paper for full details.

Even so, they are only able to give upper and lower bounds—not quite matching for a characterization. Here are their two main results:

The amazing thing about both the old and the new results is that they seem like they should not hold. Why should intersecting over machines be the key step in getting a complexity class? The authors express some doubt about whether the “unnatural” diagonalizing they construct should really be allowed. However, to exclude them by fiat would add unnatural conditions to the definition of Kolmogorov complexity itself. We (Dick and Ken) add that it is satisfying to get natural uniform complexity classes out of the intersection, at least as bounds on it.

This last note about uniform classes speaks to possible larger significance. Any computable pseudo-random generator will have to have range disjoint from any . Since is large, it makes an effective statistical test to distinguish the range of the generator from the uniform distribution. However, if is a language in a class to which we wish to apply de-randomization, but there is a such that does not reduce to , then we cannot simulate the effect of this statistical test. Thus the upper bounds in the main theorems represent limitations on the size of complexity classes whose relationships can be affected by uniform hardness assumptions.

We also wonder, if the upper bound on the second main theorem can be improved to so that it matches the lower bound, whether that can help make further progress on lower bounds for itself.

Open Problems

Eric, Luke, and Bill list as open questions whether one can remove the “” term from the middles of the main results, and whether one can replace by the original Kolmogorov complexity notion which doesn’t require to implement a prefix code. There is one other “game-changing” trick in their proof which we have omitted here, namely changing the oracle from to a related set, and it is open how far this matters.

Of course their main open question is, can the -to- and -to- bounds be tightened? What about , does it equal ?

Is there a better way to judge the true power of random strings? Can this help for general lower bounds?

[changed “and” to “and/or” after Eric for three results; some format fixes.]