A conversation about complexity lower bounds, IV

This is the fourth part of a dialogue between three characters (a mathematical optimist who likes to suggest approaches to problems), (a more sceptical mathematician who knows a small amount of theoretical computer science), and (an onlooker who occasionally asks for more detail, and occasionally makes comments about what and say). They are discussing the possibility of proving lower bounds for computational complexity. wanted at first to prove that PNP, but has now been persuaded that proving a lower bound for formula size is a more realistic target, at least for the time being, and is still a major unsolved problem. In part II of the conversation, proposed trying to show that the dual of the norm of a low-complexity function cannot be too large, at least when has order of magnitude . Numerous problems have been identified with this approach, but the idea has not yet been completely killed off. We return to the conversation as a new topic is introduced. This instalment is shorter than average, so I’ll probably post the next instalment sooner than average.

*****************************************************

You know, something has been bothering me about our discussion so far.

You’ve made that pretty clear.

I’m not talking about the fact that you don’t have any heuristic argument in favour of the dual norm being a useful complexity measure, but about something else that would be equally fundamental to any lower bound proof.

What’s that?

Well, you haven’t said how you would go about proving that some function in NP has a large norm.

A conversation about complexity lower bounds, III

The story so far: , and have been discussing how it might be possible to prove lower bounds for formula or circuit complexity. They have come to some understanding of what a proof could not be like, and in particular they have looked at examples of proof attempts that are ruled out by the result of Razborov and Rudich on natural proofs. But has proposed basing a proof on the dual of the norm, with around Several observations have been made that suggest that this is very unlikely to work, but the approach has not been definitively killed off. In the next stage of the conversation, our characters investigate the approach in more detail, finding further ways to attack it. They end on an optimistic note, but that optimism will be shaken in later instalments of the dialogue.

Incidentally, I’ve decided to let the rate that I post instalments be governed by the statistics: when they suggest that most people who are going to read an instalment have done so, then I’ll post the next one. It’s not an exact science, of course.

*************************************************

Before we dismiss the norm for unbounded as a useful complexity measure, it still seems worth thinking about the following problem.

Problem. Let and be two Boolean functions. If and , then how big can be?

I suppose quite a nice feature of that problem is that you can start right at the bottom, with .

A conversation about complexity lower bounds, continued

This is the second part of a dialogue in which three characters, , 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 has drawn attention to the work of Razborov and Rudich that places very serious constraints on what any proof that PNP 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.

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.

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.

A conversation about complexity lower bounds

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

Possible future Polymath projects

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.

PCM errata III

A quick note to say that I’ve just been asked by PUP to send all the corrections I have, so I have sent the corrections that are listed in comments on the post PCM errata II. Further errata should therefore ideally be pointed out here. I think this means that a reprint with corrections should appear in the next few months, but I’m not sure of the exact time scale.

Once again, many thanks to those who have notified me of errors. Particular thanks this time round go to Axel Boldt, who sent a very long list. He was to PCM errata II as Joseph Myers was to PCM errata I. But others too made observations that will lead to significant improvements when the reprint comes out. It has been disconcerting to see just how many mistakes remained after the effort we spent on eliminating them, but I suppose in a book this size it is inevitable, and I imagine that there are several more lurking there. So do please continue to let me know of any errors that you find. At some point in the not too distant future I’ll try to merge the second list with the first to make it easier for people to see which mistakes have already been spotted. For now, after the break, here is a copy of the instructions I have sent to PUP.

The next phase of Polymath

After the surprising success of the collaborative attack on the density Hales-Jewett theorem, many people have asked me when there would next be a Polymath project. The answer, I hope, is that it will be some time in October, though it may even be sooner if Gil Kalai goes ahead with his proposal to tackle the polynomial Hirsch conjecture polymathematically. There are many issues that seem worth discussing before further Polymath projects get going, and Terence Tao has set up a new Polymath blog in order for such discussions to take place, and also, at some point, to host the projects themselves.

So if you have any views about this, then please go over there and join the discussion. The kinds of questions we are discussing are things like how we should choose the next project, whether there are enough potential participants to support more than one project at once, whether anything can (or should) be done to broaden participation and make it easier for more people to keep up with what is going on, and so on. One obvious question is whether the blog format is the right one. However, that is not one of the main questions under discussion at the moment. Almost certainly it will become one after a few more projects have been attempted and we’ve gained a bit more experience in this way of doing things, but for now the blog, for all its limitations, seems a reasonable way of continuing.

Help — I’m stuck in my ivory tower!

The UK Qualifications and Curriculum Authority is considering introducing a new A’level course (in Britain, A’level is the exam that is taken at the end of high school) called “Use of Mathematics”. As one might expect, this idea has not met with universal approval, and there is now a campaign to stop the idea in its tracks. (I should warn you that the preceding link is to a Word file rather than to a web page.)

The General Secretary of the National Association of Headteachers has this to say to the campaigners:

They should get down from their ivory towers. They should be out in the world where young people live and exist and they should be appreciative that young people have great skills in the use of technology and we have to latch on to that.

We cannot continue teaching an out dated 19th century curriculum. This is simply turning many children off education because it is completely not relevant to them at all.

Some sample papers for the new course have been made available, so let’s have a look at the up-to-date 21st-century curriculum that will enthuse a new generation of British schoolchildren. I’ll concentrate on one or two questions but if you want to see more, then the sample papers can be found at the bottom of this page. (Update: unfortunately, these sample papers have been taken down. I can’t help wondering why. Further update: at least some sample papers are now available at the bottom of this page.)

A mathematician watches tennis

Because the French Open and Wimbledon have been available on the BBC website I’ve been watching a lot of tennis recently. And as I do so I can’t help thinking about whether mathematics has anything to say about the tactics that the players should adopt in various situations. And the more I think (or rather, idly muse) about this question, the more it becomes clear that the modelling problem it presents is a pretty hard one. Most of this post will be a discussion of questions rather than a serious attempt to supply answers.

Just to make the discussion more concrete, here are a couple of more specific questions, which I’ll come back to later. The first one is fairly simple.

1. It is generally held to be a slight advantage to serve first in a set. The reasoning goes like this. Let’s suppose (for simplicity) that the game goes with serve till 4-4. If you are serving first, then you will be in a very dangerous position if your serve is broken, since you will then have to break back immediately or lose the set. However, at least you won’t have lost. By contrast, if you are serving second and the score is 4-5, then you can’t afford to be broken — if you are broken then you lose the set and do not get even a small chance to redeem yourself. And if you have just broken your opponent so that it’s 5-4, then you still have the task of serving for the set.

However, a simple model would suggest that this reasoning is flawed. If you have a probability of winning a game on your serve and a probability of winning it on your opponent’s serve, then over the next two games you have a probability of winning both, of winning one, and of losing both, and the order the games are played in makes no difference.

DHJ write-up and other matters

This short post is in response to Jozsef Solymosi’s request for a new DHJ thread, since the previous one has become rather long and unwieldy. We’ve stopped numbering comments now, and the main purpose of the post is so that people can continue the discussion of the write-up of the proof of DHJ(k). Thanks mostly to the efforts of Ryan O’Donnell, we now have a complete draft. See also this write-up of DHJ(3) by Jozsef.

While I’m writing, I thought I’d take the opportunity to say that I am not intending to post much over the next two or three months, either here on on the Tricki. That’s because I have three more or less completed research projects that need to be properly finished (one of which is DHJ) and I owe it to my coauthors to get them done. So the plan is to clear my backlog over the summer and then come back, refreshed and ready to go, in the autumn. At that point I plan several Tricki articles (more advanced than most of the ones I’ve written so far). I also plan to start a new polymath project. Or rather, I have a file in which I have written plans for ten polymath projects, so what I’ll probably do is explain briefly what they are and try to get some idea of what appeals to people most. I am excited about several of these possible projects, so whatever we do I will be disappointed about the ones we don’t do. I may well have an online vote about it, but first I have to decide what the results of the vote will be.