This post is intended as a launch of Polymath9. I have no idea how the project will go, but I think it may be rather short lived, since the difficulties I am having at the moment look as though they could turn out to be serious ones that rule out any approach along the lines I have been thinking about. However, it is difficult to say that with any certainty, because the approach is fairly flexible, so even if the precise statements I have been trying to prove are false, it might be possible to come up with variants that are true. In a way I find that a good state of affairs, because it increases the chances of proving something interesting. Obviously it increases the chances of proving that PNP if one has more ways of attacking the problem. (I’m not claiming that it increases the probability to one that is not small — just that it increases it.) But it also increases the chances of what I would regard as a very nice consolation prize if, as expected, the approach does not work, namely a new barrier to proving that PNP. I don’t think it would be as fundamental a barrier as the three main barriers discovered so far, since it would not be showing that existing methods cannot work. Rather, it would be saying, “Here’s something we could try. Oh dear, it doesn’t work.” But as long as that something was reasonably general, I think its failure to work could be interesting enough to publish.
I’ve thought a little about what phrase to attach to the project (the equivalent of “density Hales-Jewett” or “Erdős discrepancy problem”). I don’t want to call it “P versus NP” because that is misleading: the project I have in mind is much more specific than that. It is to assess whether there is any possibility of proving complexity lower bounds by drawing inspiration from Martin’s proof of Borel determinacy. Only if the answer turned out to be yes, which for various reasons seems unlikely at the moment, would it be reasonable to think of this as a genuine attack on the P versus NP problem. So the phrase I’ve gone for is “discretized Borel determinacy”. That’s what DBD stands for above. It’s not a perfect description, but it will do.
For the rest of this post, I want to set out once again what the approach is, and then I want to explain where I am running into difficulties. I’m doing that to try to expose the soft underbelly of my proof attempt, in order to make it as easy as possible for somebody else to stick the knife in. (One could think of this as a kind of Popperian method of assessing the plausibility of the approach.) Another thing I’ll try to do is ask a number of precise questions that ought not to be impossible to solve and that can be thought about in isolation. Answers to any of these questions would, I think, be very helpful, either in demolishing the approach or in advancing it.
Reminder of basic definitions
This section is copied from my previous post.
I define a complexity structure to be a subset of a set . I call the union of the the alphabet associated with the structure. Often I consider the case where . The maps between complexity structures that I consider (if you like, you can call them the morphisms in my category) are maps such that for each , the coordinate depends only on . To put that another way, if is another complexity structure, the maps I consider are ones of the form . I have found it inconvenient not having a name for these, but I can’t think of a good one. So I hereby declare that when I use the word “map” to talk about a function between complexity structures, I shall always mean a map with this property.
I call a subset of a complexity structure basic if it is of the form for some and some . The motivation for the restriction on the maps is that I want the inverse image of a basic set to be basic.
The non-trivial basic sets in the complexity structure are the coordinate hyperplanes and . The circuit complexity of a subset of measures how easily it can be built up from basic sets using intersections and unions. The definition carries over almost unchanged to an arbitrary complexity structure, and the property of maps ensures that the inverse image of a set of circuit complexity has circuit complexity at most .
Given a complexity structure , we can define a game that I call the shrinking-neighbourhoods game. For convenience let us take to be for some positive integer . Then the players take turns specifying coordinates: that is, they make declarations of the form . The only rules governing these specifications are the following.
- Player I must specify coordinates from to .
- Player II must specify coordinates from to .
- At every stage of the game, there must be at least one that satisfies all the specifications so far (so that the game can continue until all coordinates are specified).
Note that I do not insist that the coordinates are specified in any particular order: just that Player I’s specifications concern the first half and Player II’s the second.
To determine who wins the game, we need a payoff set, which is simply a subset . Player I wins if the sequence that the two players have specified belongs to , and otherwise Player II wins. I call a set I-winning if Player I has a winning strategy for getting into and II-winning if Player II has a winning strategy for getting into . (Just in case there is any confusion here, I really do mean that is II-winning if Player II has a winning strategy for getting into . I didn’t mean to write .)
Because the game is finite, it is determined. Therefore, we have the following Ramseyish statement: given any 2-colouring of a complexity structure , either the red set is I-winning or the blue set is II-winning. (Normally with a Ramsey statement one talks about containing a structure of a certain kind. If we wanted to, we could do that here by looking at minimal I-winning and minimal II-winning sets.)
Given a complexity structure , I define a lift of to be a complexity structure together with a map that satisfies the condition set out earlier. I define a lift to be Ramsey if is a winning subset of whenever is a winning subset of , and moreover it is winning for the same player. A more accurate name would be “winning-set preserving”, but I think of “Ramsey” as an abbreviation for that.
This gives us a potential method for showing that a subset is I-winning: we can find a Ramsey lift such that is simple enough for it to be easy to show that it is a I-winning subset of . Then the Ramsey property guarantees that , and hence , is I-winning in .
The definition of a Ramsey lift is closely modelled on Martin’s definition of a lift from one game to another.
What I would love to be able to show
Suppose that we have a suitable definition of “simple”. Then I would like to prove the following.
- If a set has polynomial circuit complexity, then there exists a Ramsey lift of with such that is simple and the cardinality of is much less than doubly exponential.
- If is a random subset of , then with high probability the smallest Ramsey lift that makes simple has an alphabet of doubly exponential size.
- There exists an NP set such that
the smallest Ramsey lift that makes simple has an alphabet of doubly exponential size.
Obviously, the first and third statements combined would show that PNP. For the time being, I would be delighted even with just the first of these three statements, since that would give an example of a property of functions that follows non-trivially from low circuit complexity. (That’s not guaranteed, since there might conceivably be a very simple way of constructing lifts from circuits. However, I think that is unlikely.)
Having the first and second statements would be a whole lot better than just having the first, since then we would have not just a property that follows non-trivially from low circuit complexity, but a property that distinguishes between functions of low circuit complexity and random functions. Even if we could not then go on to show that it distinguished between functions of low circuit complexity and some function in NP, we would at least have got round the natural-proofs barrier, which, given how hard that seems to be to do, would be worth doing for its own sake. (Again this is not quite guaranteed, since again one needs to be confident that the distinguishing property is interestingly different from the property of having low circuit complexity.)
As I said in my previous post, I think there are three reasons that, when combined, justify thinking about this potential distinguishing property, despite the small probability that it will work. The first is of course that the P versus NP problem is important and difficult enough that it is worth pursuing any approach that you don’t yet know to be hopeless. The second is that the property didn’t just come out of nowhere: it came from thinking about a possible analogy with an infinitary result (that in some rather strange sense it is harder to prove determinacy of analytic sets than it is to prove determinacy of Borel sets). And finally, the property appears not to be even close to a natural property in the Razborov-Rudich sense: for one thing it quantifies over all possible complexity structures that are not too much bigger than , and then it demands that the maps should preserve the I-winning and II-winning properties.
It is conceivable that the property might turn out to be natural after all. For instance, maybe the property of preserving I-winning and II-winning sets is so hard to achieve (I have certainly found it hard to come up with examples) that all possible Ramsey lifts are of some very special type, and perhaps that makes checking whether there is a Ramsey lift that simplifies a given set possible with a polynomial-time algorithm (as always, polynomial in ). But I think I can at least say that if the above property is natural, then that is an interesting and surprising theorem rather than just a simple observation.
An approach that initially looked promising, but that ran up against a serious difficulty
Let be a straight-line computation of a set . That is, each is either a coordinate hyperplane (a set of the form for some and some ), or the intersection or union of two earlier sets in the sequence, and . We would like to find a complexity structure with not too large, together with a map that has the properties required of a Ramsey lift, such that is simple. Since a composition of Ramsey lifts is a Ramsey lift, and since taking inverse images (under the kinds of maps we are talking about) preserves simple sets, whatever definition of “simple” we are likely to take, as well as preserving all Boolean operations, a natural approach is an inductive one. The inductive hypothesis is that we have found a Ramsey lift such that the sets are simple for every . We now look at . By the inductive hypothesis, this is a union or intersection of two simple sets, so we now look for a Ramsey lift such that is simple. Setting , we then have a Ramsey lift such that is simple for every .
Thus, if we can find a very efficient Ramsey lift that turns a given intersection or union of two simple sets into a simple set, then we will be done. “Very efficient” means efficient enough that repeating the process times (where is polynomial in — though even superlinear in would be interesting) does not result in an alphabet of doubly exponential size. Note that if our definition of “simple” is such that the complement of a simple set is simple, then it is enough to prove this just for intersections or just for unions.
What might we take as our definition of “simple”? The idea I had that ran into trouble was the following. I defined “simple” to be “basic”. I then tried to find a very efficient lift — I was hoping to multiply the size of the alphabet by a constant — that would take the intersection of two basic sets to a basic set.
Let us very temporarily define a basic set to be -basic if it is defined by means of a restriction of the th coordinate. That is, it is of the form . (I want this definition to be temporary because most of the time I prefer to use “-basic” to refer to an intersection of at most basic sets.) If is -basic and is -basic, then it is natural to expect that if we can lift to a basic set, that basic set should be either -basic or -basic. Furthermore, by symmetry we ought to be able to choose whether we want it to be -basic or -basic. But then if we let be the 1-basic set and let be any other basic set, that tells us that we can lift so that it becomes a 1-basic set.
Now let us apply that to the coordinate hyperplanes in . If we can lift these very efficiently one by one until they all become 1-basic sets, then we have a complexity structure with a small alphabet and a map such that is 1-basic for every coordinate hyperplane . But applying Boolean operations to 1-basic sets yields 1-basic sets, and every subset of is a Boolean combination of coordinate hyperplanes. Therefore, every subset of has become a 1-basic set!
This is highly undesirable, because it means that we have shown that the property “Can be made simple by means of an efficient Ramsey lift” does not distinguish functions of low circuit complexity from arbitrary functions.
Because of that undesirability, I have not tried as hard as I might have to find such a lift. An initial attempt can be found in this tiddler. Note that the argument I have just given does not show that there cannot be a Ramsey lift that turns an -basic set into a 1-basic set at the cost of multiplying the size of the alphabet by a constant. What I have shown is that if this could be done, then there would be a Ramsey lift that converted all sets simultaneously into 1-basic sets, with an alphabet of size at most . If that were the case, then I think the approach would be completely dead. (Correction: the approach if the sets to be preserved are I-winning and II-winning sets would almost certainly be dead, and I don’t have any reason to think that if one tried to preserve other classes of sets, then the situation would be any different.) So that is one possible way to kill it off.
Problem 1. Let be a complexity structure and let be a basic subset of . Must there exist a complexity structure and a Ramsey lift such that is 1-basic and ?
In fact, if all one wants to do is disprove the statement that for a random set there is a doubly exponential lower bound, it is enough to obtain a bound here of the form .
The above observation tells us that we are in trouble if we have a definition of “simple” such that simple sets are closed under unions and intersections. More generally, we have a problem if we can modify our existing definition so that it becomes closed under unions and intersections. (What I have in mind when I write this is the example of basic sets. Those are not closed under intersections and unions, but if one could prove that every intersection of two basic sets can be lifted to a basic set, then, as I argued above, one could probably strengthen that result and show that every intersection of two basic sets can be lifted to a 1-basic set. And the 1-basic sets are closed under intersections and unions.)
Before I go on to discuss what other definitions of “simple” one might try, I want to discuss a second difficulty, because it gives rise to another statement that, if true, would deal a serious blow to this approach.
In the previous post, I gave an example of a lift that provides us with what I think of as the “trivial upper bound”: a Ramsey lift that turns every single subset of into an -basic set, with an alphabet of doubly exponential size. So if we want an inductive argument of the kind I have discussed above, we will need to show that an intersection or union of two simple sets can be lifted to a simple set with the size of the alphabet increasing in such a way that if one iterates that increase polynomially many times, the resulting size will be less than doubly exponential. (Actually, that isn’t quite necessary: maybe we could establish a lower bound of for a function in NP and an upper bound of for functions of circuit complexity , where .) This makes it highly problematic if we want to do anything that squares the size of the alphabet after only polynomially many steps. If we do that, then the size of the alphabet after times that polynomial number of steps, which is of course still a polynomial number of steps, will be at least and we will have proved nothing.
The reason this is troubling is that even if I forget all about simplifying any set , I find it very hard to come up with examples of Ramsey lifts. (All I mean by a Ramsey lift of is a complexity structure and a map that takes I-winning sets to I-winning sets and II-winning sets to II-winning sets.) The only ones I know about can be found on this tiddler here. And they all have the property that the players have to provide “extra information” of a kind that at the very least squares the size of the alphabet. In fact, it is usually quite a lot worse than that.
Maybe I can try to be slightly more precise about what I mean there. All the lifts I have considered (and I don’t think this is much of a restriction) take the form of sets where a typical sequence in is of the form and the map takes that sequence to . If , then What makes it interesting is that we do not take all sequences of the above form (that is, for arbitrary and arbitrary . Rather, we take only some of those sequences. (It is that that makes it possible to simplify sets. Otherwise, there would be nothing interesting about lifts.) So if Player I makes an opening move , we can think of this as a move in the original game together with a binding obligation on the two players that the eventual sequence will have at least one preimage such that . The set of all such sequences is a set that may well be a proper subset of .
Suppose now that this extra information is enough to determine some other coordinate . Then unless there are already very few options for how to choose , the number of possibilities for will be comparable in size to the size of the alphabet, and therefore the size of the alphabet is in serious danger of squaring, and certainly of raising itself to the power 3/2, say. And that is, as I have just pointed out, much too big an increase to iterate superlinearly many times.
So it looks as though any “extra information” we declare has to be rather crude, in the sense that it does not cut down too drastically the set in which the game is played. But I have no example of a Ramsey lift with this property. What’s more, the kind of difficulty I run into makes me worry that such a lift may not exist. If it doesn’t, then that too will be a serious blow to the approach.
Let me ask a concrete problem, the answer to which would I think be very useful. It is a considerable weakening of Problem 1.
Problem 2. Let be a complexity structure. Does there necessarily exist a non-trivial Ramsey lift with and bounded above by a function of ?
The main concern is that should not depend on .
I have not sorted out completely what “non-trivial” means here, but let me give a class of examples that I consider trivial. Let be a large enough set and let be a surjection. Define a map by . Finally, let . Then we can think of as a map from to . Note that is in some sense just like : it’s just that the coordinates of may have been repeated.
I claim that this is a Ramsey lift. Indeed, suppose that is a I-winning subset of . Then a winning strategy for Player I for is simply to project the game so far to , play a winning strategy in , and choose arbitrarily how to lift each specification of a coordinate of to a specification of the corresponding coordinate of .
To put that more formally, if the specifications so far are for and it is Player I’s turn, then she works out the specification she would make in in response to the specifications for . If this specification is , then she picks an arbitrary preimage of and makes the specification .
A similar argument works for winning sets for Player II.
It is the fact that this can always be done that makes the lift in some sense “trivial”. Another way of thinking about it is that there is an equivalence relation on such that replacing a point by an equivalent point makes no difference.
As far as I can tell at this stage, the problem is interesting if one takes “non-trivial” to mean not of the form I have just described. However, I reserve the right to respond to other examples by enlarging this definition of triviality. The real test of non-triviality is that an interesting Ramsey lift is one that has the potential to simplify sets.
A positive answer to the problem above will not help us if is an enormously large function of . However, for now my main concern is to decide whether it is possible to obtain a bound independent of . If it is, then a major source of worry is removed. If it is not, then the approach will be in serious trouble.
A simple observation
I stopped writing for a few hours after that last paragraph, and during those few hours I realized that my definition of non-triviality was not wide enough. Before I explain why not, I want to discuss a worry I have had for a while, and a very simple observation that explains why I don’t have it any more.
Because the worry was unfounded, it is rather hard to explain it, but let me try. Let’s suppose that we are trying to find an interesting Ramsey lift . Suppose also that we choose a random subset of with the critical probability . That is, we choose elements with that probability that makes the probability that is a I-winning set equal to . Then it seems highly likely that will be “only just” a I-winning set if it is one. And we’ll need to make sure that every time just happens to be I-winning, then is I-winning, and every time it just fails to be I-winning, is II-winning. This seems extraordinarily delicate, unless somehow the winning strategies in are derived rather directly from the winning strategies in (as seems to be the case for the examples we have so far).
The observation I have now made is almost embarrassingly simple: if is only just a I-winning set, we do not mind if is a II-winning set. That is because is not usually the complement of . In fact, if is a random set and every element of has many preimages in , then both and will be pretty well all of .
It is worth drawing attention to the way that it seems to be most convenient to prove that a lift is Ramsey. Instead of taking a winning subset of and trying to prove that its image is winning (for the same player) in , I have been taking a winning subset of and trying to prove that its inverse image is winning (for the same player) in . Let me prove a very easy lemma that shows that this is OK.
Lemma. Suppose that is a lift. Then the following two statements are equivalent.
(i) The image of every winning subset of is winning in for the same player.
(ii) The inverse image of every winning subset of is winning in for the same player.
Proof. Suppose that the second condition holds and let be a winning subset of . If is not a winning subset of for the same player, then is a winning subset of for the other player, which implies that is a winning subset of for the other player. But , so this contradicts being a winning set for the original player.
Conversely, suppose that the first condition holds and let be a winning subset of . Then if is not a winning subset of for the same player, then is a winning subset of for the other player, which implies that is a winning subset of for the other player. But , so this contradicts being a winning set for the original player. QED
Another way of saying all this is that if we want to prove that a map is a Ramsey lift, then the only winning sets for which we need to prove that is also a winning set are inverse images of sets . And the reason for that is that one can replace by the superset without affecting the image.
A slightly less trivial, but still uninteresting, class of Ramsey lifts
The quick description of these is as follows: take a trivial Ramsey lift of the kind I described earlier (one that duplicates each coordinate several times) and pass to a random subset of it.
Let me sketch an argument for why that, or something similar to it, works. The reason is basically the same as the reason that the trivial lift works. For the sake of clarity let me introduce a little notation. I’ll start with a complexity structure . I’ll then take to be a random subset of , where is some set and I write a typical element of as a sequence . The map takes this sequence to . I’m thinking of as a fairly large set, and the elements of are chosen independently from with some suitable probability .
Now let be a winning subset of . I want to show that is a winning subset of for the same player. So let be a winning strategy for for Player I (the case of Player II is very similar, so I won’t discuss it). Then in she can play as follows. If it is her turn and the specifications so far are of for , then she looks at what the strategy dictates in in response to the specifications of the , ignoring the . This will involve specifying some . Now she must find some such that there exists a sequence in that satisfies the specifications so far as well as the specification .
Typically, the proportion of that will serve as a suitable is approximately , so what we need, roughly speaking, is that should be bigger than . It’s not quite as simple as that, since if the alphabet is very very large, then there may be occasional pieces of extraordinary bad luck. However, I’m pretty sure it will be possible to modify the above idea to make it watertight.
A wider definition of non-triviality
Let and be complexity structures and a Ramsey lift. Let us say that is trivial if for any set of specifications () that can arise during the game in , for any set of specifications () with (this is a slight abuse of notation) and for any further specification , there exists a further specification , consistent with all the previous ones, such that .
This is an attempt to describe the property that makes it very easy to lift strategies in to strategies in : you just see what you would do at each stage in and lift that to — a policy that does not work in general but works in some simple cases.
One thing that is probably true but that it would be good to confirm is that a Ramsey lift of this simple kind cannot be used to simplify sets. I’ll state this as a problem, but I’m expecting it to be an easy exercise.
Problem 3. Let be a lift that is trivial in the above sense. Is it the case that for every the straight-line complexity of is equal to the straight-line complexity of ?
(A quick reminder: in a general complexity structure, I define the straight-line complexity of a set to be the length of the smallest sequence of sets that ends with , where all earlier sets in the sequence are either basic sets or unions or intersections of two earlier sets.)
Assuming that the answer to Problem 3 is yes, then the next obvious question is this. It’s the same as Problem 2 except that now we have a candidate definition of “non-trivial”.
Problem 4. Let be a complexity structure. Does there necessarily exist a non-trivial Ramsey lift where the size of the alphabet goes up by at most a factor that depends on only?
I very much hope that the answer is yes. I was beginning to worry that it was no, but after the simple observation above, my perception of how difficult it is to create Ramsey lifts has altered. In that direction, let me ask a slightly more specific problem.
Problem 5. Is there a “just-do-it” approach to creating Ramsey lifts?
What I mean there is a procedure for enumerating all the winning sets in and then building up and in stages, ensuring for each winning set in turn that its inverse image is a winning set for the same player. I would be surprised if this could be done efficiently, but I think that it would make it much clearer what a typical Ramsey lift looked like.
Let me also recall a problem from the previous post.
Problem 6. Let be the set of all sequences in of odd parity. Does there exist a Ramsey lift such that is a basic set and the alphabet of is not too large?
I would also be interested in a Ramsey lift that made simple in some other sense. Indeed, I suspect that the best hope for this approach is that the answer to Problem 6 is no, but that for some less restrictive definition of “simple” it is yes.
Matters of procedure
Maybe that’s enough mathematics for one post. I’d like to finish by trying to clarify what I mean by “micro-publication” on the TiddlySpace document. I can’t do that completely, because I’m expecting to learn on the job to some extent.
I’ll begin by saying that Jason Dyer answered a question I asked in the previous post, and thereby became the first person to be micro-published. I don’t know whether it was his intention, but anyway I was pleased to have a contribution suitable for this purpose. He provided an example that showed that a certain lift that turns the parity function into a basic function was (as expected) not a Ramsey lift. It can be found here. There are several related lifts for which examples have not yet been found. See this tiddler for details.
Jason’s micro-publication should not be thought of as typical, however, since it just takes a question and answers it. Obviously it’s great if that can be done, but what I think of as the norm is not answering questions but more like this: you take a question, decide that it cannot be answered straight away, and instead generate new questions that should ideally have the following two properties.
- They are probably easier than the original question.
- If they can be answered, then the original question will probably become easier.
One could call questions of that kind “splitting questions”, because in a sense they split up the original task into smaller and simpler tasks — or at least there is some chance that they do so.
What I have not quite decided is what constitutes a micro-publication. Suppose, for example, somebody has a useful comment about a question, but does not generate any new questions. Does that count? And what if somebody else, motivated by the useful comment, comes up with a good question? I think what I’ll probably want to do in a case like that is write a tiddler with the useful comment and the splitting question or questions, carefully attributing each part to the person who contributed it, with links to the relevant blog comments.
Also, I think that when someone asks a good question, I will automatically create an empty tiddler for it. So one way of working out quickly where there are loose ends that need tying up is to look for empty tiddlers. (TiddlySpace makes this easy — their titles are in italics.)
Some people may be tempted to think hard about a question and then present a fairly highly developed answer to it. If you feel this temptation, then I’d be very grateful if you could do one of the following two things.
- Resist it.
- Keep a careful record of all the questions you ask in the process of answering the original question, so that your thought processes can be properly represented on the proof-discovery tree.
By “resist it”, what I mean is not that you should avoid thinking hard about a question, but merely that each time you generate new questions, you should write up your thoughts so far in the form of blog comments, so that we get the thought process and not just the answer. The main point is that if we end up proving something interesting, then I would like it to be as clear as possible how we did it. With this project, I am at least as interested in trying to improve my understanding of the research process as I am in trying to make progress on the P versus NP problem.