Archive for September, 2009

A conversation about complexity lower bounds, continued

September 28, 2009

This is the second part of a dialogue in which three characters, :), 8) and :|, discuss issues connected with the P versus NP problem. There are now nine parts: if this number continues to increase at a faster rate than I post them, then I may have to increase the rate of posting.

The story so far: πŸ™‚ has put forward one or two ideas, and 8) has drawn attention to the work of Razborov and Rudich that places very serious constraints on what any proof that P\neNP could possibly look like. This makes precise an intuition that πŸ™‚ had been beginning to build up after several failed attempts to find such a proof. πŸ™‚ then enthusiastically discusses further possible applications of the basic idea of Razborov and Rudich (seemingly unaware that Razborov and Rudich themselves had had similar but much more precise thoughts of the kind), before retiring to think for a while about what a “non-natural” proof might look like.


πŸ™‚ Hi again.

8) Hello. Got anything for us today?

πŸ™‚ I’m not really sure. But I have had a few thoughts that I’d like to try out on you.

8) Fire away.

πŸ™‚ Well, the result of Razborov and Rudich tells us that if we want to define some notion of “structure” or “simplicity” that all functions of low complexity have and some function in NP does not have, then we have a choice. Either almost all functions must be simple, or it must not be possible to decide in polynomial time whether a function is simple. I have to say that I rebel against the first, so I’ve been trying to come up with properties that one might be able to prove something about, despite their not being in P. (more…)

A conversation about complexity lower bounds

September 22, 2009

In my previous post, I suggested several possible Polymath projects. One of them, which initially seemed to be the favourite (and was my own favourite) was to have a look at an idea I had had for getting round the Razborov-Rudich obstacle to proving lower bounds in computational complexity. (This is closely related to the P versus NP problem, though my idea did not obviously apply to that problem itself.) However, now I am fairly sure I have understood why it cannot work: somehow, even if you come up with an idea for a proof that is not directly ruled out by their result, you find that slightly more complicated arguments, based on their idea, do eventually show that it doesn’t work.

While thinking about my approach, I wrote what was intended to be a series of five initial posts for the Polymath project if it happened. I thought I would experiment, so instead of explaining the basic concepts in the usual way I wrote a dialogue, which I hoped would be easier to read. It is between three characters, who are denoted by smileys (or is that smilies? no, perhaps not). The main character, :), is a mathematical optimist, continually becoming enthusiastic about ideas that have not been fully thought through. The next character, 8) , is much more sceptical, and also knows more about computational complexity (a lot less than an expert in the area, but enough to merit a “cool” smiley). Finally, 😐 is a neutral observer who occasionally asks for fuller explanations when πŸ™‚ or 8) seem to be omitting them, and sometimes makes easy but useful mathematical observations.

To some extent these characters, particularly the first two, represent different sides of me as I think about the problem. However, I do not always agree with what they say (sometimes this is obvious, since they do not always agree with each other), and I sometimes allow them to get things wrong, or to think that they have had an idea when in fact that idea is already known. For example, towards the end of this first part of the conversation, πŸ™‚ has the idea of applying the insights of Razborov and Rudich to other computational models. Not surprisingly, πŸ™‚ was not the first to think of doing that, as an internet search later revealed.

Since I wrote the post about Polymath projects, the conversation has expanded and is now in seven parts of about 5000 words each. Be warned in advance that pretty well every idea that πŸ™‚ has is eventually doomed to fail. But I hope that non-experts will find the failure instructive even if experts just find it wearily familiar.

I also hope that some of the later parts of the conversation might lead to fruitful exchanges of comments even if they don’t lead to a proper Polymath research project. For instance, at least at the time of writing, I don’t have completely satisfactory general explanations for why some of :)’s approaches fail. And some of the heuristic arguments (of which there are many) presented here are open to criticism. (Another warning: some of the early arguments are definitely wrong, even when the three characters appear to take them seriously, and their wrongness is pointed out only quite a bit later. It may be a little unconventional to explain mathematics by putting forward incorrect ideas and correcting them only after their consequences have been explored in detail, but there are plenty of conventional accounts of computational complexity for those who want them.)

For these kinds of reasons, it seems to me that I might as well post the dialogue rather than letting it go to waste. It’s even conceivable that somebody will be prompted by the ideas here to have better ideas, in which case maybe something serious could come out of it after all. I plan to post the seven parts (or more if I continue to add to them) of the dialogue at a rate of about one a week, to keep this blog ticking over until I am ready to start a Polymath project on something else. The first part is very much an introduction. (more…)

Possible future Polymath projects

September 16, 2009

I am still very busy at the moment and do not expect to be able to get down to any serious polymathematics for a few weeks, at least. And in any case, there are two Polymath projects going on at the moment, so I am not in a huge hurry to start another. (The projects are Gil Kalai’s on the polynomial Hirsch conjecture and Terence Tao’s on finding primes deterministically.)

Having said that, a common complaint about the first Polymath project was that it got started so rapidly that it was very easy to get left behind. So for my next project I would like to do two things. First, I want to get a sense of which, out of many potential projects I have in mind, would appeal to enough other people for there to be a good chance of finding a core of people ready to put in an effort similar to the effort that some people put into DHJ. (A similar core of regular contributors has developed for Terry’s polymath4: I wonder if this will happen for all projects that get off the ground.) And secondly, having chosen a new project, I want to write several introductory posts to give people a chance to get up to speed before the project properly starts. The way things are looking at the moment, I think it’s unlikely that I’ll start a project before November, but the preliminary posts might come out earlier.

In this post, I will say very briefly what some of these possible projects are, and will also report on a conversation I had recently with Jordan Ellenberg, during which he told me some thoughts about Polymath that I found extremely interesting. In fact, let me do that first. (more…)