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.

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.

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.

Complexity Classes of the Week: SBP and A0PP

Previous CCW

Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's take a look.

Böhler, Glaßer and Meister present a new class SBP that can be defined as follows. A language L is in SBP if there is a #P function f and an FP function g such that for all x,

1. if x is in L then f(x)>g(x), and
2. if x is not in L then 0≤f(x)<g(x)/2.

Vyalyi introduces a class A₀PP which has exactly the same definition except #P is replaced by Gap-P. [If I lose you in alphabet soup in this post, you can use the zoo to keep up.]

In both classes the "2" in the definition can be replaced by 2^|x|k for any fixed k.

SBP sits between MA and AM, a rare natural class between these two. SBP is also contained in BPP_path but there is a relativized world where it is not contained in Σ₂, giving a relativized answer to the open question in my CCW on BPP_path. SBP is closed under union but whether it is closed under intersection remains open even in relativized worlds.

QMA, the quantum version of MA, is contained in A₀PP, which itself is contained in PP. If A₀PP = PP then PH is in PP. He claims this gives evidence that QMA is not PP but given strong pseudorandom function, PH is in PP. But co-NP is probably not in QMA which is evidence enough for me that QMA is not equal to PP.

To prove his later result, Vyalyi notes that P^#P[1] is in SPP^C₌P and he shows that SPP^A₀PP is contained in PP and his result follows since C₌P is in PP and by Toda's Theorem PH is in P^#P[1].

Paddable NP-Complete Sets are Isomorphic

By request, here is a sketch of the proof of the Berman-Hartmanis 1978 result that all paddable NP-complete sets are isomorphic. The proof builds on an old result of Myhill that all r.e.-complete sets are recursively isomorphic. Since nearly all natural NP-complete sets are paddable then they are also isomorphic.

First some definitions:

• A set A is paddable if there is a polytime computable function p:Σ^*×Σ^*→Σ^* such that
  1. For all x and y, x is in A if and only if p(x,y) is in A.
  2. p is 1-1 and |p(x,y)|>|x|+|y|.
  3. p is computable in polynomial-time.
  4. p is invertible on its range in polynomial-time.
• Sets A and B are isomorphic if there is a reduction u from A to B such that
  1. u is a reduction: For all x, x is in A if and only if u(x) is in B.
  2. u is 1-1 and onto.
  3. u and its inverse are both computable in polynomial time.

Suppose A and B are paddable NP-complete sets. Let f reduce A to B and g reduce B to A. Let p be a padding function for A and q a padding function for B. Let r(x)=q(f(x),x) and s(y)=p(g(y),y). The function r is a 1-1 length-increasing efficiently-invertible-on-its-range reduction from A to B and s is the same from B to A.

Now we can define our isomorphism u(x) from A to B.

• If x is not in the range of s then let u(x)=r(x).
• If x is in the range of s, let y be such that s(y)=x.
• If y is not in the range of r then let u(x)=y.
• If y is in the range of r, let z be such that r(z)=y.
• Recursively compute u(z).
• If u(z)=y then let u(x)=r(x) otherwise let u(x)=y.

Since r and s are length-increasing, the depth of the recursion is at most the length of x so u is computable in polynomial time. I'll leave it to the reader to verify that u is an isomorphism.

The Turing Award

As noted in a comment to the last post, it is now official that Ron Rivest, Adi Shamir and Len Adleman won the 2002 Turing Award.

Unfortunately outside of computer science and particularly outside academics the Turing award is not so well known or respected. In 1987, I was a graduate student visiting my old fraternity at Cornell, Anne Marie Hopcroft came in. Anne Marie was dating one of the fraternity brothers at the time. "My father won the Turing Award! My father won the Turing Award!", she exclaimed. Nobody, besides myself, seemed the least bit interested. She and I tried to explain the importance of the award but to no avail. Had her father won the Nobel prize, you could be sure the reaction would have been different.

The 1997 movie Good Will Hunting gave great publicity for mathematics much by explaining the importance of the Fields Medal to the masses. What can we do to make the Turing Award better known?

Awards

The ACM doctoral dissertation award, given to the best doctoral thesis in computer science, was awarded to Venkatesan Guruswami for his thesis "List-Decoding on Error-Correcting Codes". Another theorist, Tim Roughgarden, was one of the runners-up. This was definitely a great year for theory Ph.D. theses.

Rumors are flying that theorists Ron Rivest, Adi Shami and Len Adleman won the Turing Award for their work on the RSA cryptosystem. The Turing Award is the highest honor in computer science, the closest we have to a Nobel prize.

Finding Problems to Work On

Often graduate students ask me for a good problem to work on. This is one of the biggest challenges of an advisor. A good problem for a graduate student must fulfill each of three characteristics.

1. Open.
2. Doable.
3. Interesting.

Finding problems that fit any two of these three is not hard, but if a problem is doable and interesting, someone likely would have solved it by now. Too often interesting is the property that is given the least emphasis.

I generally give the advice that my advisor, Michael Sipser, gave to me. Pick up a proceedings of a recent conference in your area and read through the abstracts of papers until you find one that interests you. The "interests you" part is important, for without it you won't have the motivation to study further.

Read the paper thoroughly. Read related papers. If you lose interest, start the process all over again.

Once you've read several papers in an area that interests you talk about it with your advisor and your fellow graduate students. Some of these papers might list open questions and you could work on those. You might say, "Karp listed this as an open question, and if Karp can't solve it why should I be able to?" Karp is a very smart but also very busy person. It is unlikely he spent more than an hour thinking hard about these questions. As a graduate student you can spend much more time focusing on these problems and could easily make more progress than someone like Karp could.

Even better is to formulate your own problems. Perhaps there is an interesting variation in a model that the original paper, for whatever reason, did not cover. Perhaps you can find connections between two papers that no one had noticed before. These are great problems to work on: As you are breaking new ground, theorems can start flowing like water. Just remember not to have too much weirdness in your questions; keep the research interesting.

Articles on Quantum and DNA Computers

A couple of interesting pieces in the New York Times.

Jim Holt reviews George Johnson's A Shortcut Through Time: The Path to the Quantum Computer. I haven't seen Johnson's book yet but the more I read about the more I recommend it to laypeople who are interested in quantum computers. It really seems like he gives an understanding of quantum computation without overly hyping the topic.

There is also an article from the circuits section on new work on at the Weizmann Institute on DNA computers. As typical with articles on DNA computing in the New York Times, you should read the end of the article first. That way you get the reality before the hype.

Razborov on Unprovability

In the old commenting system, Daniel Varga had the following comment on my post on unprovability.

I guess Alexander Razborov turned to the study of Propositional Proof Systems because he wanted to prove that "proving SAT is not in P/poly" is hard in a formal sense. What is his opinion about undecidability? (Of course I know I should ask him, but he doesn't have such a nice message board. :))

I passed the question to Razborov and here is his response.

Dear Daniel, First, I understand that "undecidability" in your question should read "unprovability" (or, otherwise, I misunderstood it). And the answer to it very much depends on the strength of the formal theory we are interested in. For classical theories like Peano Arithmetic or Set Theory I do not have enough intuition (not even to mention evidence) to articulate any opinion. The only thing which seems quite sure to me is that such an independence result, if true, would not be much easier to prove than the original P vs. NP question itself... If we, however, descend in the logical hierarchy to weaker theories capturing poly-time computations (commonly known as Bounded Arithmetic), the answer becomes quite different. I do conjecture that "SAT is not in P/poly" is independent from these theories. Moreover, I believe that if we allow ourselves a standard cryptographic assumption (FACTORING is hard, for definiteness) this question might be more attainable with currently known techniques than those discussed above. Further, I expect that if we ever manage to prove such an independence result, its proof would be very illuminating in approaching the question "what's next and what are we missing?" (cf. Natural Proofs). Finally, let me mention that the introduction to the paper "Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution" (available from my Web site) contains an expanded version of some of these views. Alexander.

Comments

Because of the popularity of the war weblogs, the Haloscan commenting system I was using was being overloaded which would on occasion cause my web log to have errors and require a long time to load. To avoid this I'm now using cgiComments which I am hosting myself.

The major negative is that I have lost all of the old comments. I apologize for this. Please feel free to repost your old comments or add new ones.

Computation Beyond Turing Machines?

In the April issue of the Communications of the ACM, Peter Wegner and Dina Goldin have a technical opinion entitled Computation Beyond Turing Machines. From the article: "Turing machines are inappropriate as a universal foundation for computational problem solving and computer science is a fundamentally non-mathematical discipline". Those are fighting words and luckily I have this weblog to fight back.

Wegner and Goldin's main argument is summed up towards the end of the article. "In the last two decades, computing technology has shifted from mainframes and microstations to networks and wireless devices, with the corresponding shift in applications from number crunching and data processing to embedded systems and graphical user interfaces. We believe it is no longer premature to encompass interaction as part of computation. A paradigm shift is necessary in our notion of computational problem solving, so it can provide a complete model for the services of today's computing systems and software agents."

In here they have a good point. The area of human-computer interaction is sometimes more art than science. But while the basic model of the Turing machine is a sequential device, theoretical computer scientists have come up with variations that capture networks and other aspects of interaction, some of which are described in the Wegner-Goldin article. And all of these new models can be simulated by Turing machines. The Turing machine remains supreme as the model that captures all computation.

Far more troubling is the following: "Gödel had shown in 1931 that logic cannot model mathematics and Turing showed that neither logic nor algorithms can completely model computing and human thought." This is a complete misreading of Gödel and Turing. Not every mathematical statement has a logical proof, but logic does capture everything we can prove in mathematics, which is really what matters. Likewise, Turing machines captures everything we can compute. And what we can compute is what computer science is all about.

Math Riots Prove Fun Incalculable

My post on Fermat's last theorem last week reminded me of my personal all-time favorite math parody, a Chicago Tribune column written by Eric Zorn.
Zorn, grandson of the mathematician Max Zorn, wrote this column that put Wiles' proof of Fermat in a context of the Chicago Bulls basketball team winning a recent championship. I was in the CS department at the University of Chicago during that time and the parallels hit home for me: "Andrew Wiles" = "Michael Jordan", "Yoichi Miyaoka" = "Charles Barkley", "Rie-Peat" = "Three-peat", "Doing set theory in a New Jersey library" = "Gambling in Atlantic City", etc. You get the picture.
Or maybe you had to be there. After this article made the email rounds, one European professor asked me if there really were graduate students rioting in Chicago. Go figure.

Big Ideas

"The Institute" in yesterday's post refers to the The Institute for Advanced Study, a fully-endowed facility devoted to fundamental research. WNET, the New York public television station, has produced a four-part series about the institute and its research. The first episode of "Big Ideas" airs Thursday night in New York. You'll need to watch your listings to see when it is playing on your local station.

Counterexample to Fermat's Last Theorem Found!!!

There has been a really amazing development today on Fermat's Last Theorem. Noam Elkies has announced a counterexample, so that FLT is not true after all! His spoke about this at the Institute today. The solution to Fermat that he constructs involves an incredibly large prime exponent (larger that 10^20), but it is constructive. The main idea seems to be a kind of Heegner point construction, combined with an really ingenious descent for passing from the modular curves to the Fermat curve. The really difficult part of the argument seems to be to show that the field of definition of the solution (which, a priori, is some ring class field of an imaginary quadratic field) actually descends to Q. I wasn't able to get all the details, which were quite intricate...
So it seems that the Shimura Taniyama conjecture is not true after all. The experts think that it can still be salvaged, by extending the concept of automorphic representation, and introducing a notion of "anomalous curves" that would still give rise to a "quasi-automorphic representation".

---

This is an email I received indirectly from the late Gian-Carlo Rota dated April 2, 1994. The historical context: In June of 1993, Andrew Wiles announced that he had proven Fermat's Last Theorem but later that year a subtle bug was found which was not fixed until September of '94.
So in April of 1994 we didn't know whether Wiles' proof was valid and given the date was April 2 and how well the email was written, many mathematicians believed this message. But of course it was all an elaborate April Fools joke.