Could anything like Deolalikar’s strategy work?

This post comes with the same warning as my previous one: my acquaintance with the ideas of Deolalikar’s paper is derived not from the paper itself (apart from a glance through it to get some kind of general impression) but from some of the excellent commentary that has been taking place on the blogs of Dick Lipton and Scott Aaronson. One comment that many people, including me, have found very useful has been one of Terence Tao, who attempted to summarize the state of the discussion up to the time he made the comment. Here is a portion of his summary.

The paper introduces a property on solution spaces, which for sake of discussion we will call “property A” (feel free to suggest a better name here). Formally, a solution space obeys property A if it can be efficiently defined by a special family of LFP formulae, the monadic formulae (and there may be additional requirements as well, such as those relating to order). Intuitively, spaces with property A have a very simple structure.
Deolilakar then asserts
Claim 1. The solution space to P problems always obey property A.
Claim 2. The solution space to k-SAT does not obey property A.

The latest from Dick Lipton’s blog seems to be that Neil Immerman has identified two serious flaws with Deolalikar’s proof. However, Tao, commenting on that, has pointed out that Deolalikar’s general strategy has not yet been shown to be hopeless in the way that, say, an attempted natural proof would have been shown to be hopeless by Razborov. In this post, I’d like to argue that it might be hopeless. I’m not sure I can say what that means in the abstract, so let me just give the argument.

First, here is a slightly more detailed version of Tao’s summary, provided on Dick Lipton’s blog by Albert Atserias.

If I may I would rephrase the thing as follows. Let “polylog-parametrizable” be a property of solution spaces yet to be defined.

Claim 1: The solution spaces of problems in P are polylog-parametrizable.

Claim 2: The solution space of k-SAT is not polylog-parametrizable.

Now, Claim 1 could be split as follows:

Claim 1.1: The solution spaces to problems in Monadic LFP are polylog-parametrizable.

Claim 1.2: Every problem in LFP reduces to a problem Monadic LFP by a reduction that preserves polylog-parametrizability of the solution spaces.

From these Claim 1 would follow from Immerman-Vardi Theorem (we need successor or linear order of course).

Perhaps Claim 1.1 could be true (we know a lot about Monadic LFP, in particular unconditional lower bounds using Hanf-Gaifman locality). But Claim 1.2 looks very unlikely. The reduction that Deolalikar proposes is standard but definitely does not preserve anything on which we can apply Hanf-Gaifman locality.

What I would like to do here is attempt to reinforce Atserias’s conclusion, by explaining why it seems to me very unlikely, unless somebody can tell me an amazing idea that gets round the problem (that is an important qualification, since one’s mathematical intuition can certainly be affected by unexpected ideas) that Claim 1.2 could be true. To do that, I’ll exhibit a specific problem in P that just doesn’t feel as though it could be reduced.

All this is completely independent of what any of the words in Atserias’s summary mean. I don’t know what polylog-parametrizability is (my comfort here is that I know of nobody apart from Deolalikar who does), or what the Immerman-Vardi theorem states, or what Hanf-Gaifman locality or monadic LFP are. And one thing Deolalikar’s paper has done is make me quite curious about these concepts and results. But for the purposes of this discussion, all that really matters is that polylog-parametrizability should mean something vaguely like what its name suggests.

OK, the problem in P I have in mind is this. Let me start with the following model of a random circuit (which I have discussed before in my sequence of “conversations between smileys” about the P versus NP problem in late 2009). Start with a 01 sequence of length (which we think of as the input). Now at each step of the computation, perform the following process. Choose three random numbers between 1 and (that is, choose a subset of of size 3 uniformly at random), and a random bijection Now apply to the values of the sequence at those three numbers. That is, if we choose with then take the 01-sequence apply to it, and put the transformed sequence back in places , and

Now just repeat this process for, say, steps. Define the output of the function to be the value of the first term of the sequence once this process has finished.

Not very much has been proved rigorously about functions like this, but what little is known points to a conclusion of the following kind: their solution spaces (that is, the set of input sequences that give rise to a 1) are very very hard to distinguish from random subsets of This provides a rather useful sanity check for any proposed proof that PNP. It is similar to the natural-proofs barrier, but with the important disadvantage of not being rigorous. And it goes something like this: if I have a property that is supposed to distinguish between the solution spaces of problems in P and the solution space of at least one other problem, is it at least plausible that this property applies to the solution spaces of random computable functions (defined according to the above model) if and only if it applies to random functions? If so, then the failure of the property at some specific problem in NP has to be a rather particular to that problem in NP. (This is similar to Razborov and Rudich’s requirement that a property that distinguishes P from NP should either be very strange, or else should apply to almost all functions — not including some specific function in NP.)

Now whatever polylog-parametrizability might mean, it doesn’t sound like something that would apply to a purely random function. Indeed, Tao describes it as a “simplicity” property. This already worries me — why doesn’t Deolalikar’s argument fall foul of the natural-proofs barrier?

The suggested answer to this is that Deolalikar uses uniformity in an essential way. Note that the random computable functions I defined above are not uniform — I was giving a different circuit (or rather, something that can easily be realized by a circuit) for each But I find it incredibly unlikely that this makes a serious difference, since I could always generate the circuits pseudorandomly in some silly way. For instance, I could use digits of to help me make my random choices. Will that suddenly make the solution space far nicer than it was before? I don’t think so.

Now Deolalikar could simply counter that, whether I like it or not, he has found a simplicity property of pseudorandom computable functions. But if that assertion is in doubt, then it is legitimate to step back and consider the general strategy, as I am now doing, and ask whether something might conceivably be salvaged from Deolalikar’s proof attempt. And I have tried to present reasons to be pessimistic about this.

I don’t feel as though the arguments in this post are watertight. Indeed, somewhere I read a rather sophisticated comment (which I cannot relocate) about how Deolalikar might be evading the natural-proofs barrier, and it may be that a similar comment would deal with my worries. Also, my total lack of understanding of any of the logic and finite model theory used in the argument means that I am not properly taking account of the possibility that the property involves some kind of trace that a function in P has of how it has been put together. (However, if I was given the solution space of a pseudorandomly computable function in P, I wouldn’t fancy my chances of reconstructing the circuit that led to it …)

So to finish with, here are my main two questions. Apologies if they have already been answered in other places.

1. Is polylog-parametrizability supposed to be a “simplicity” property that applies to functions in P but not to random functions?

2. If so, then can anyone give me a half-plausible idea of how it might distinguish between a function computed by a pseudorandom circuit of length and a genuinely random function?

I have a feeling that the answer to 1 may in fact be no, and that Deolalikar is claiming that almost all functions are simple, but that at a certain critical probability random k-SAT has very delicate features that are shared by very few functions and that make it complex. But I’d still like to be sure about this.