It seems that the informal argument in my previous post may have been aiming off target. Here is a sort of counter to it, by Jun Tarui. (See also this earlier comment of his, and the ensuing discussion.)
If I’ve understood various comments correctly, Deolalikar is making a move that I, for one, had not thought of, which is to assume that P=NP and derive a contradiction. How could that help? Well, it allows us to strengthen any hypothesis we might like to make about polynomial-time computable functions to one that is preserved by projection.
Let me spell that out a bit. Suppose that is a polynomial-time computable function on bits, where is at most polynomial in Then we can fix a set of bits, and for each we can ask the question, “Does there exist such that ?” (By I mean the sequence that agrees with on and with on ) And we can set if and only if the answer is yes.
Now these functions belong to NP (provided the choice of is made uniform in some way or other, but let me for now ignore the distinction between uniformity and non-uniformity). So if P=NP then they belong to P. To see this intuitively, note that if you are provided with and merely asked to verify that then you can do so in polynomial time (since by hypothesis is in P). That makes belong to P as well if P=NP.
Note that the solution sets of the functions are projections of the solution space of (the obvious projection from to ).
So it may be that Deolalikar is saying not that functions in P have some simplicity property (polylog parametrizability) but that functions with all their projections in P have this property. And a random function in P will then not be relevant, since its projections definitely don’t look as though they belong in P.
Terence Tao has a suggestion for dealing with this, which is to observe that if is smaller than then the function does belong to P after all, since we can just go through all possible and see whether they work. But if is bigger than then with immensely high probability there does exist such that so the function should be more or less trivial. (Of course, given that we have in mind a function that is not genuinely random, this probabilistic argument is not rigorous, but it seems extremely likely that its conclusion is correct.)
Playing Deolalikar’s advocate for a bit, let me see whether there might be a way to wriggle out of this. It occurs to me that he might consider adding a sparseness hypothesis: instead of looking at arbitrary polynomial-time computable functions, let’s concentrate on functions that are 1 only rather infrequently. Note that if you want to create an interesting function in NP, then this is a very natural restriction: it stops all the fibres containing a 1 and making the projection trivial.
It’s easy to create a pseudorandom function with this sparseness: whereas before I suggested doing a sequence of random bijections on triples of coordinates and then taking the value of the first coordinate, now I would suggest doing a sequence of bijections as before and taking the function to be 1 if and only if the first coordinates are equal to 1 after the bijections have been performed. The result is a function that should be 1 with density about
If we now do a projection to a set of size then it will be 1 with probability about so it will be far from trivial. But checking for a satisfying assignment (that is, a such that ) by brute force now takes time
So here is a proof strategy for Deolalikar to which I don’t see an immediate objection along the lines I have been proposing (which does not rescue Deolalikar’s argument from the many other objections, but I still find it of some small interest). We shall try to find a simplicity property of polynomial-time computable functions with the following properties.
(i) They take the value 1 with exponentially small density.
(ii) They are reasonably uniform. (This is to avoid a function that is just an ordinary random computable function of the first bits, provided the last bits are all equal to zero.) That is, there are no “nice” sets on which their density is much bigger than exponentially small.
(iii) All their projections belong to P as well.
This is all very well and good, but what should the simplicity property be, and how does one use the vitally important hypothesis that the projections are in P? Well, I’m imagining that Deolalikar’s answer to the latter is something to do with finite model theory. For instance, perhaps in some sense the projections “ought” to be introducing an existential quantifier, so if they don’t, then it “ought” to be saying something pretty strong about the function, if we use a logical characterization of P. (Unfortunately, I don’t understand anything about finite model theory, so I can’t be more detailed here.) Perhaps this allows him to conclude that a function with properties (i)-(iii) has a simplicity property that k-SAT at the critical density lacks.
Let me make very clear that I am not endorsing Deolalikar’s argument. This post is more about me than about the argument: it is saying that I no longer have my own pet explanation for why a proof of this general kind could not possibly work. But that is a very far cry from saying that the vague outline above can be turned into a proof: I don’t have the faintest idea how to get from the finite model theoretic characterization of P (which I cannot even state) to something about polylog parametrization (the definition of which I do not understand).
Update. On thinking about this a little further, I now think that even a more sophisticated approach such as I have outlined above will run into very serious difficulties, which are basically the same difficulties as before but pushed to a different place. To see this, let us consider the contrapositive of the statement one would need to prove.
First, for clarity’s sake, here is the statement itself (not in precise form): if is a function in P (perhaps satisfying certain extra conditions that are satisfied by random k-SAT) and all its projections are also in P, then has a structure that random k-SAT lacks.
It seems to me that this statement is equivalent to the following (also not completely precise) statement: there exists a projection of k-SAT with some property that functions in P lack.
If so, then we still have to decide what that property is. If it is a simplicity property, then we appear to be doomed for the reasons outlined in my previous post.
Why did I say that the two statements “seemed to be” equivalent? I did so because there just conceivably might be some magic that gets from the property that all projections are in P to some global simplicity property. So one might end up needing to show merely that random k-SAT lacked the global property. But I’m not sure that really helps, since again the contrapositive will show that any function that lacks the global simplicity property has a projection that has a property not shared by any function in P. What is that property?
Without a pretty amazing answer to that question, I go back to feeling that no argument along these lines can succeed.