Update

Many drafts existed, with a few changes between them. But it seems Deolalikar did not provide a list of the change. Using pdftotext and diff, I will try to state every change between the file on this pages.

Caution

I will give the page number of the more recent of the two version, usually there may be up to 2 or 3 pages of difference, but finding the correct page between many version is not hard.

Since there was a change between the pages number, and some definition's number changed, diff give a lot of false positive. I try as much as possible to remove false positive, and to give an output easy to read by human, which means I may forgot a little change which seems to be a false positive, hence if you realize I forgot something, please correct.

Change between First draft and pnp_updated.pdf Second draft

He added an introduction

Here I quote KWRegan

The pagination is identical on page 77. On page 78 top, he has deleted the sentence “In the ENSP model, the covariates are recovered by restricting to the first n vertices in the bottom row, but now we have a graphical model that can represent the underlying computation done in order to get to that final state.”

Then after the main proof, on pp84-85, he had added one paragraph:

“It is also useful to consider how many different parametrizations a block of size poly(log n) may have. Each variable may choose poly(log n) partners out of O(n) to form a potential. It may choose O(log n) such potentials. Even coarsely, this means blocks of variables of size poly(log n) only “see” the rest of the distribution through equivalence classes that grow as O(npoly(log n))). This quantity would have to grow exponentially with n in order to display the behavior of the d1RSB phase. Once again we return to the same point — that the jointness of the distribution that a purported LFP algorithm would generate would lie at the poly(log n) levels of conditional independence, whereas the jointness in the distribution of the d1RSB solution space is truly O(n). Namely, there are irreducible interactions of size O(n) that cannot be expressed as interactions between poly(log n) variates at a time, and chained together by conditional independencies as would be done by a LFP. This is central to the separation of complexity classes. Hard regimes of NP-complete problems allow O(n) variates to irreducibly jointly vary, and accounting for such O(n) jointness that cannot be factored any further is beyond the capability of polynomial time algorithms.” This seems intended to address the actual deterministic lower bound on SAT that would be obtained. This might be obtainable by generalizing Immerman-Vardi to DTIME[t(n)] for some robust collection of time bounds t(n) > poly(n); in a comment above I meant to speculate that 2^{n^{o(1)}} would do. (I should point out that in the uniform setting unlike with circuits, lower-bounding against that does not imply a lower bound of “2^{n^\epsilon} for some epsilon > 0″, though the proof still could establish this stronger bound.) I’d be interested to know if there is any other difference between the drafts.

“it can only display a limited behavior.” became “it can only display a limited joint behavior.”

Change between pnp_updated.pdf Second draft and np_updated-mjr.pdf draft 2 + &epsilon

(new version of 09-Aug-2010 20:21 659K)

added page 43-44 he changed between "those that follow from Gaifman's theorem. " and the lemma 4.8 is new

Page 73, he changed between " extended to a satisfying assignment." and "Since we want to generate exponentially"

Added "As mentioned earlier, "

Page 86 was changed after " then this means"