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 + ε

(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"

Change betwen 2+&epsilon and draft 3

Disparition of 2.6

Chapter 3 is new but take part of 2.6

A lot of change in the Abstract

6.2.2 title became: Performance of Known Algorithms in the d1RSB Phase

8.1 became :Measuring Conditional Independence in Range Limited Models

1.1: added "For ease of presentation, we will assume our variables are binary." then page 6 and 7 are almost entirely new. The part beginning by "At this point we begin to see" until "measure the size of these interactions." was removed. Page 9 "We take a geometric picture of a monadic LFP" the word monadic is new. same thing on "monadic LFP relies" Last paragraph of page 9 changed.

Page 10 the "two properties" are new (in fact the first one was already stated, the second is really new) "and blocks of n variables are instantiated cn distinct ways under these strong correlations. Namely, we have ample, and highly correlated distributions having no factorization into conditionally independent pieces (remember the value limited case is already ruled out since the distribution is ample). " is new

Page 11 after "between the clusters" is new until "Finally, as the clause density increases " The paragraph beginning by "We should stress that the picture" is new " when we build models for the range limited interactions that occur during monadic LFP. " is new " for range limited models" is new

Paragraph begining by "The crucial property that allows us to analyze mixtures" had changed

At the end of the introduction, he added: "It also completes this picture, since it says that extensive O(n) correlations that (a) can- not factor through conditional independencies and (b) are amply instantiated, are the source of failure of polynomial time algorithms.

"The central concern of this work has been to understand what are the irreducible interactions between the variables in a system — namely, those that cannot be" became "Our central concern with respect to range limited models is to understand which variable interactions in a system are irreducible — namely, those that cannot be"

Page 60 beginning with "At this point, we are now working with k-tuples" until the end of the subsection is rewritten/new. Page 62 "making the distribution of solutions poly(log n)-parametrizable. Likewise, value limited interactions in higher arity LFP computations also lead to distribution of solutions that are poly(log n)-parametrizable." is new.

Corollary 6.2 until "we end" is new. The section changed a lot from this place to the end of the sub subsection

Section 6.2.2 changed a lot

page 73 "The original work reported in [MPZ02] was on 3-SAT." is new

" variable are ample-O(n)" the word "ample" is new.

A lot of change at begin of section 8.5, at end of page 98 and page 99

Introduction of chapter 8 is longer. Remarque 8.1 changed a lot. Section 8.5 changed a lot.

" Theorem 7.6. A global relation R is computable in polynomial time if and only if R is inductive." became "Theorem 8.7. A global relation R on a class of successor structures is computable in polynomial time if and only if R is inductive."

Many change in theorem 8.10's proof