Deolalikar P vs NP paper

From Polymath Wiki
Jump to navigationJump to search

This is a clearinghouse wiki page for aggregating the following types of items:

  1. Analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP;
  2. News and information about this preprint;
  3. Background material for the various concepts used in the preprint; and
  4. Evaluation of the feasibility and limitations of the general strategies used to attack P != NP, including those in the preprint.

It is hosted by the polymath project wiki, but is not a formal polymath project.

Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions or speculations are to be avoided. This page is derived from an earlier collaborative document created by Suresh Venkatasubramanian.

Discussion threads

The main discussion threads are being hosted on Dick Lipton's blog. Several of the posts were written jointly with Ken Regan.

The paper

These links are taken from Vinay Deolalikar's web page.

Here is the list of updates between the different versions.

Typos and minor errors

Any typos appearing in an earlier draft that no longer appear in the latest draft should be struck out.

  • (Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via Blake Stacey)
  • (Second draft) Some (but not all) of the instances of the [math]\displaystyle{ O() }[/math] notation should probably be [math]\displaystyle{ \Theta() }[/math] or [math]\displaystyle{ \Omega() }[/math] instead, e.g. on pages 4, 9, 16, 28, 33, 57, 68, etc. (via András Salamon)
    • Still present in the third draft, e.g. "O(n) Hamming separation between clusters" occurs on page 68 and similarly in several other places.
  • (Second draft, page 27) [math]\displaystyle{ n 2^n }[/math] independent parameters → [math]\displaystyle{ n 2^k }[/math] independent parameters
    • Still present in third draft, but now on page 33.
  • (draft 2 + e, p.34, Def. 3.8): [math]\displaystyle{ n }[/math] → [math]\displaystyle{ k }[/math]
    • Still present in third draft, but now on page 49 and Def 4.8.
  • (Second draft, page 52) [math]\displaystyle{ \sum C_{li}S_i-k\gt 0 }[/math] → [math]\displaystyle{ \sum C_{li}S_i+k\gt 0 }[/math]
    • Still present in third draft, but now on page 70.
  • (draft 2 + e, p.10): "We reproduce the rigorously proved picture of the 1RSB ansatz that we will need in Chapter 5." The phrasing makes it sound like we will need the 1RSB ansatz in Chapter 5 instead of saying that it is reproduced in Chapter 5 (which I think is what the author intended). One fix is to move "in Chapter 5" to the beginning of the sentence.
    • Still present in third draft, but now on page 16 (and referring to Chapter 6 instead).
  • (Third draft, p. 102): "inspite" → "in spite".
  • (Third draft, p. 27, first paragraph): "is to obtain" → "to obtain".
  • (Third draft, p. 19) Should the neighborhood [math]\displaystyle{ {\mathcal G}_i }[/math] be [math]\displaystyle{ {\mathcal N}_i }[/math] instead (or vice versa)? Also, this neighborhood contains self-loops and so is technically not a neighborhood system in the sense of Definition 2.3.
  • (Third draft, p. 20) Some braces appear to be missing in the first display (just before Definition 2.6).
  • (Third draft, p. 24) Some text appears to be obscured by Figure 2.2.
  • (Third draft, p. 25) In (2.1) and (2.2) [math]\displaystyle{ \phi }[/math] should probably be [math]\displaystyle{ \phi_3 }[/math].
  • (Third draft, p. 37) Some text appears to be obscured by Figure 3.2.
  • (Third draft, p. 43) "The Tarski-Knaster" → "The Tarski-Knaster theorem".
  • (Third draft, p. 44) Right parenthesis missing in (4.3) and immediately afterwards.
  • (Third draft, p. 99) Some italicized text appears to be obscured by Figure 8.2.

Proof strategy

(Excerpted from this comment of Ken Regan)

Deolalikar has constructed a vocabulary V which apparently obeys the following properties:

  1. Satisfiability of a k-CNF formula can be expressed by NP-queries over V—in particular, by an NP-query Q over V that ties in to algorithmic properties.
  2. All P-queries over V can be expressed by FO(LFP) formulas over V.
  3. NP = P implies Q is expressible by an FO(LFP) formula over V.
  4. If Q is expressible by an LFP formula over V, then by the algorithmic tie-in, we get a certain kind of polynomial-time LFP-based algorithm.
  5. Such an algorithm, however, contradicts known statistical properties of randomized k-SAT when k >= 9.

An alternate perspective

Leonid Gurvits:

...the discrete probabilistic distributions in the paper can be viewed as tensors, or very special multilinear polynomials. The assumptions “P=NP” somehow gives a (polynomial?) upper bound on the tensor rank. And finally, using known probabilistic results, he gets nonmatching (exponential?) lower bound on the same rank.

If I am right, then this approach is a very clever, in a good sense elementary, way to push the previous algebraic-geometric approaches.

Specific issues

  • P=NP only gives polylog parameterizability property of a lift of the k-SAT solution space, rather than that solution space itself If P=NP, then the procedure in Section 8.3 of the third draft does not create a polylog parameterizable distribution on the solution space of a hard phase k-SAT problem itself, but rather on a lift of that solution space in which many additional variables are added, so that one is now working in [math]\displaystyle{ \{0,1\}^N }[/math] for some [math]\displaystyle{ N=n^{O(1)} }[/math] rather than in [math]\displaystyle{ \{0,1\}^n }[/math]. Of course, one can forget all but the original n variables and return to a distribution on the solution space by projecting, but it is not clear that the polylog parameterizable property is preserved by this (there is no reason why the directed acyclic graph on the N literals has any meaningful projection onto the original n literals). In particular, the projected distribution is not in a recursively factorizable form, and the cluster geometry of the lifted solution space could be quite different from that of the original k-SAT problem (e.g. the set of frozen variables could change, as could the definition of a cluster, and number of flips required to get from one cluster to the next). This issue does not seem to be discussed at all in the paper.
  • The problem in the LFP section of the proof:
Anuj Dawar raises a point about order-invariance in intermediate stages of the LFP computation:

Another problem I see is the order-invariance. Deolalikar (after justifying the inclusion of the successor relation R_E) that *each stage* of any LFP formula defining k-SAT would be order-invariant. While it is clearly true that the LFP formula itself would be order-invariant, this does not mean that each stage would.

So, it seems to me that this proof shows (at best) that k-SAT is not definable by an LFP each stage of which is order-invariant. This has an easy direct proof. Moreover, it is also provable that XOR-SAT (or indeed parity) is not LFP-definable in this sense.

As phrased by Albert Atserias and Steven Lindell:

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.

(Caution: the term "solution spaces" requires some clarification. More precisely, we are looking at satisfiability problems of the form "Given x, does there exist y such that R(x,y)=1?". The solution space here refers not to the set [math]\displaystyle{ \{ x: R(x,y)=1 \hbox{ for some } y \} }[/math] of feasible x, but rather on a "typical" fibre [math]\displaystyle{ \{ y: R(x,y) = 1 \} }[/math] for a "typical" feasible x.)

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 the 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.


Specifically, (and this is adapted from Lindell's Critique) on Remark 8.5 on page 85 (third draft), it is asserted that "the [successor] relation... is monadic, and so does not introduce new edges into the Gaifman graph". However, this is only true in the original LFP. When encoding the LFP into a monadic LFP as is done immediately afterwards in the same remark, the relation becomes a section of a relation of higher arity (as mentioned in page 87 and Appendix A), using an induction relation. However, this induction relation itself must be monadically encoded, and it may not have bounded degree. In fact, because of successor, it could define an ordering in two of its columns, which would render the Gaifman graph useless (indeed, the Gaifman graph could even collapse to have diameter one).
Hanf-Gaifman locality also does not apply if we work with k-ary LFP directly without the reduction to the monadic case. Here the answer is that if we work with k-ary LFP directly then the Gaifman graph changes after each iteration of the LFP-computation because we need to take care of the new tuples that are added to the k-ary inductively defined relation. And in fact, after O(log n) iterations, the inductively defined relation could very well include the transitive closure of the given successor relation R_E, in which case the Gaifman graph is again fully connected (a clique). Once we have a clique for a Gaifman graph, we have local = global.

Neil Immerman has written a very interesting letter to Deolalikar critiquing his proof. With Immerman's permission, this letter is reproduced on the following page: Immerman's letter. Immerman also raises the problem of order-invariance mentioned by Anuj Dawar above.
  • Placeholder for specific critique based on the structure of k-XORSAT - it seems like we're ready to phrase this one.

General issues

Issues with LFP

Erich Grädel has an extensive review of finite model theory and descriptive complexity.

There appear to be three issues related to the use of the characterization of P in terms of first order logic, an ordering and a least fixed point operator. All of these are discussed in the Lipton/Regan post, with contributions from David Barrington, Paul Christiano, Lance Fortnow, James Gate, Arthur Milchior, Charanjit Jutla, Julian Bradfield and Steven Lindell.

  • Ordering, or lack thereof: Is the lack of ordering in the logical structures used to define the LFP structure a problem (since parity can not be expressed without an ordering even with LFP, hence P is not captured without order).
In chapter 7 this issue seems to disappear since he introduces a successor relation over the variables [math]\displaystyle{ x_1\lt \dots\lt x_n\lt \neg x_1\lt \dots\lt \neg x_n }[/math].
If it was possible to express k-SAT in FO(NLFP,without succ) (NLFP=non deterministic LFP) or in relational-NP, as introduced in [AVV1997] then by an extension of the Abiteboul-Vianu theorem it would be enough to prove that k-SAT is not in FO(LFP,without succ). This would avoid the problem of the order
  • The issue of tupling: The paper requires that a certain predicate in the FO(LFP) formula be unary, and forces this by expanding neighborhoods and constructing k-tuples of parameters to act as single parameters. It is not clear how this affects the arguments about the propagation of local neighborhoods.
Albert Atserias says, "...for someone knowing the finite model theory used in the paper, there is a jump in the reasoning that lacks justification. This is the jump from Monadic LFP to full LFP. The only justification for this crucial step seems to be Remark 7.4 in page 70 of the original manuscript (and the vague statement in point 3 of page 49), but this is far from satisfactory. The standard constructions of the so-called canonical structures that Vinay refers to (see Ebbinghaus and Flum book in page 54) have a Gaifman graph of constant diameter, even without the linear order, due to the generalized equalities that allow the decoding of tuples into its components. Issues along these lines were raised before here and in comment 54 here
Steven Lindell presents a detailed critique of this problem, with an indication that there might be insurmountable problems. It is reproduced here for completeness.
  • Boundedness and greatest fixed points: Charanjit Jutla has pointed out that the argument in section 4.3 (with which several other people have also had issues) depends on the absence of a greatest fixed point. "This is a usual mistake most people new to fixed-point logics fall prey to. For example, now he has to deal with formulas of the kind [math]\displaystyle{ \nu x (f(y, x) \and g(y, x)). }[/math] Section 4.2 deals with just one least fixed point operator…where his idea is correct. But, in the next section 4.3, where he deals with complex fixed point iterations, he is just hand waving, and possibly way off."
A few comments later, he appears to revise this objection, while bringing up a new issue about the boundedness of the universe relating to the LFP operator.

Issues with phase transitions

A brief synopsis of the terms discussed can be found here

  • The nomenclature of phase transitions: In the statistical physics picture, there is not a single phase transition, but rather a set of different well defined transitions called clustering (equivalently d1RSB), condensation, and freezing (Florent Krzakala and Lenka Zdeborova). In the current version of the paper, properties of d1RSB (clustering), and freezing are mixed-up. Whereas following the established definitions, and contrary to some earlier conjectures, it is now agreed that some polynomial algorithms work beyond the d1RSB (clustering) or condensation thresholds. Graph coloring provides some evidence of this when one compares the performance of algorithms with the statistical physics predictions. The property of the solution space of random K-SAT the paper is actually using is called freezing. It was conjectured in the statistical physics community (Florent Krzakala, Lenka Zdeborova and Cris Moore) that really hard instances appears in the frozen phase, i.e. when all solutions have non-trivial cores. Existence of such a region was proven rigorously by Achlioptas and Ricci-Tersenghi and their theorem appears as Theorem 5.1 in the paper.
  • The XOR-SAT objection : The conjecture that frozen variables make a problem hard is however restricted to NP-complete problems such as K-SAT and Q-COL. Indeed a linear problem such as random k-XORSAT also has a clustering transition, frozen variables, etc., and is not easy to solve with most algorithms, but is of course in P as one can use Gauss elimination and exploit the linear structure to solve it in polynomial time (Cris Moore, Alif Wahid, and Lenka Zdeborova). Similar problem might exist in other restricted CSP which are in P, but may exhibit freezing stage, as pointed by several other people.

More specifically: in the portion of the paper that is devoted to analyzing the k-SAT problem, what is the first step which works for k-SAT but breaks down completely for k-XORSAT?

  • The error-correcting codes objection: Initiated in a comment by harrison: If I understand his argument correctly, Deolalikar claims that the polylog-conditional independence means that the solution space of a poly-time computation can’t have Hamming distance O(n) [presumably he means \theta(n)], as long as there are “sufficiently many solution clusters.” This would preclude the existence of efficiently decodable codes at anything near the Gilbert-Varshamov bound when the minimum Hamming distance is large enough.

Issues with random k-SAT

Complex solution spaces are uncorrelated with time complexity. (The below is a greatly expanded version of a series of twitter comments by Ryan Williams, on twitter) The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". For certain parameterizations, the space of satisfying assignments to a random k-SAT instance has some intriguing structure. If SAT is in P, then SAT can be captured in a certain logic (equivalent to P in some sense). The author claims that anything captured in this logic can't have a solution space with this intriguing structure. There are two "meta" objections to this. One is that "intriguing structure in the solution space is not sufficient for NP hardness". The second is that "intriguing structure is not necessary for NP hardness". They don't actually point to a place where the proof is wrong. But they do appear to give an obstacle to the general proof method. They exploit the fact that the concept of a "solution space" cannot be coherently defined for NP problems, without being verifier-dependent.

How to map satisfiable formulas to trivial problems with exactly the same solution space structure. Very easy problems can also have complicated solution distributions. The following arose from discussions with Jeremiah Blocki. Here is a very easy way to (non-uniformly) map any infinite collection of satisfiable formulas into [math]\displaystyle{ SAT0 }[/math], the set of formulas satisfied by the all-zeroes assignment. The map completely preserves the number of variables, the number of satisfying assignments, the distances between assignments, the clusters--as far as I can tell it preserves every property that has been studied about random k-SAT. Observe [math]\displaystyle{ SAT0 }[/math] is trivially decidable in polynomial time. This should be a barrier to any proof of P vs NP that attempts to argue that the solution space of an NP-hard problem is "too complex" for P. (It even blocks any proof of AC0 not equal NP with this pattern!) This is the objection which is most germane to the current proposed proof: it opposes the claim that "anything in P can't have a solution space with complicated structure".
The map is simple: for a satisfiable formula F on n variables, let [math]\displaystyle{ (A_1,\ldots,A_n) }[/math] be a satisfying assignment for it, and define F' to be the formula obtained by the following procedure: flip the signs of all literals involving [math]\displaystyle{ x_i }[/math] in F iff [math]\displaystyle{ A_i = 1 }[/math]. Now the space of satisfying assignments to F is transformed by the map [math]\displaystyle{ \phi_A(x_1,\ldots,x_n) = (x_1 \oplus A_1,\ldots,x_n \oplus A_n) }[/math]. Observe this map completely preserves all distances between assignments, clusters, etc., and that the all-zeroes assignment satisfies F'. So for any infinite collection [math]\displaystyle{ {C} }[/math] of satisfiable formulas with "hard solution structure" there is also an infinite collection of formulas [math]\displaystyle{ {C'} }[/math] with analogous solution structure, where [math]\displaystyle{ C' }[/math] is a subset of [math]\displaystyle{ SAT0 }[/math].
Furthermore, the map easily extends to the generalization of k-SAT which consists of pairs [math]\displaystyle{ (F,A) }[/math], where [math]\displaystyle{ F }[/math] is a k-SAT formula, [math]\displaystyle{ A }[/math] is a partial assignment to some variables, and we wish to know if it is possible to complete the partial assignment into a full satisfying assignment. By flipping literals appropriately in [math]\displaystyle{ F }[/math], there is always an instance [math]\displaystyle{ (G,A) }[/math] where [math]\displaystyle{ G }[/math] can be satisfied by setting the rest of the variables to zero, and yet [math]\displaystyle{ G|_{A} }[/math] has an isomorphic solution space to [math]\displaystyle{ F|_{A} }[/math]. So for every instance of "k-SAT-Partial-Assignment" we can find an instance of "SAT0-Partial-Assignment" (which is again a trivial problem) with the same solution space structure.
The above looks like a cheat. Of course it is! We are exploiting the fact that, for arbitrary problems in NP (and therefore P as well), the solution space of that problem is not uniquely well-defined in general. (Hubie Chen raised a similar point in email correspondence.) A solution space for an instance can only be defined with respect to some polynomial time verifier for the problem: this space is the set of witnesses that make the verifier accept on the instance. If you change the verifier, you change the solution space. The usual solution space for SAT is just the one that arises from a verifier that checks a candidate assignment. If this verifier is used on SAT0, we get a complex solution space. If we use a sane verifier for SAT0 instead (the verifier that checks all-zeroes) then the solution space becomes trivial. However, if P=NP then there's also a verifier such that SAT has a trivial solution space, namely the verifier which ignores its witness and just runs a polynomial time algorithm for SAT. The above argument only arises because we have forced the notion of solution space to be verifier-independent over P and NP problems.
Satisfiable formulas with 'complex' solution spaces can be efficiently mapped to satisfiable formulas with 'simple' solution spaces. A hard distribution of solutions is not necessary for NP-hardness, either. A weird distribution is not what makes a problem hard, it's the representation of that solution space (e.g., a 3-CNF formula, a 2-CNF formula, etc.). The "hard" case of 3-SAT is the case where there is at most one satisfying assignment, since there is a randomized reduction from 3-SAT to 3-SAT with at most one satisfying assignment (Valiant-Vazirani). This reduction increases the number of clauses and the number of variables, but that doesn't really matter. The point is that you can always reduce 3-SAT with a "complex" solution space to one with an "easy" solution space, so how can a proof separating P from NP rely on the former? (Note that, if plausible circuit lower bounds hold up, then Valiant-Vazirani can be derandomized to run in deterministic polynomial time.) To summarize, there is essentially no correlation between the "hard structure" of the solution space for instances of some problem, and the NP-hardness of that problem.
Of course, this point on its own does not invalidate Deolalikar's approach. In principle it's possible that some NP-complete problems have complex solutions spaces and some do not. To prove just one NP-complete problem has a complex solution space would be enough if it was also proved that all P problems have simple solution spaces. For this to work, it would clearly be necessary that reductions between NP problems need not preserve complexity of solution space, but the examples given above indicate this is the case.

Uniformity issues

The following is a lightly edited excerpt from a comment of Russell Impagliazzo:

The general approach of this paper is to try to characterize hard instances of search problems by the structure of their solution spaces. The problem is that this intuition is far too ambitious. It is talking about what makes INSTANCES hard, not about what makes PROBLEMS hard. Since in say, non-uniform models, individual instances or small sets of instances are not hard, this seems to be a dead-end. There is a loophole in this paper, in that he’s talking about the problem of extending a given partial assignment. But still, you can construct artificial easy instances so that the solution space has any particular structure. That solutions fall in well-separated clusters cannot really imply that the search problem is hard. Take any instance with exponentially many solutions and perform a random linear transformation on the solution space, so that solution y is “coded” by Ay. Then the complexity of search hasn’t really changed, but the solution space is well-separated. So the characterization this paper is attempting does not seem to me to be about the right category of object.

Locality issues

From a comment of Thomas Schwentick:

There is an another issue with the locality in remark 3 of Section 4.3. Moving from singletons to tuples destroys locality: this is because the distance of two tuples is defined on the basis of its participating elements. For example, if two tuples have a common element then their distance is (<=) 1. Thus, even if in the "meta-structure" two tuples are far apart, they can be neighbors because of their singular elements.

See also the tupling issues mentioned in an earlier section.

From a comment of Russell Impagliazzo:

The paper talks about “factoring” the computation into steps that are individually “local”. There are many ways to formalize that steps of computation are indeed local, with FO logic one of them. However, that does not mean that polynomial-time computation is local, because the composition of local operations is not local. I’ve been scanning the paper for any lemma that relates the locality or other weakness of a composition to the locality of the individual steps. I haven’t seen it yet.

Does the argument prove too much?

From a comment of Cristopher Moore:

The proof, if correct, shows that there is a poly-time samplable distribution on which k-SAT is hard on average — that hard instances are easy to generate. In Impagliazzo’s “five possible worlds” of average-case complexity, this puts us at least in Pessiland. If hard _solved_ instances are easy to generate, say through the “quiet planting” models that have been proposed, then we are in Minicrypt or Cryptomania.

Barriers

Any P vs NP proof must deal with the three known barriers described below. The concerns around this paper have, for the most part, not yet reached this stage yet.

Relativization

Quick overview of Relativization Barrier at Shiva Kintali's blog post

Natural proofs

See Razborov and Rudich, "Natural proofs" Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (1994).

(Some discussion on the uniformity vs. non-uniformity distinction seems relevant here; the current strategy does not, strictly speaking, trigger this barrier so long as it exploits uniformity in an essential way.)

In this blog post, Tim Gowers points out an "illegitimate sibling" of the natural proofs obstruction that seems to apply to any attempt to separate complexity classes by trying to exploit the fact that the solution spaces of problems Q in easy complexity classes enjoy some simple structural property (which for sake of argument we will call "property A"). To begin with, let us use a simple notion of solution space, namely the space of all x for which the problem Q(x) has an affirmative answer (but note that this is not the notion of solution space used in Deolalikar's paper). Then the argument goes as follows. Consider a "pseudorandom polynomial circuit" [math]\displaystyle{ f: \{0,1\}^n \to \{0,1\} }[/math] formed by applying a polynomially large (e.g. [math]\displaystyle{ n^{100} }[/math]) number of reversible logical gate operations on the n-bit input string, and then outputting (say) the first bit of the final state of that n-bit string as output. It is plausible that this function is pseudorandom enough that it is indistinguishable from a random function [math]\displaystyle{ g: \{0,1\}^n \to \{0,1\} }[/math]. In particular, if f obeys property A, then a random function should also obey property A. However, most reasonable candidates for property A constrain the structure of the solution space to the extent that the random function should not obey property A. This strongly suggests that property A cannot contain all problems in P. To put it another way, any argument that proceeds by distinguishing easy and hard solution spaces should be able to describe a criterion that can distinguish the functions f and g from each other.

As pointed out by Jun Tarui, Deolalikar's argument is not directly analysing the solution space [math]\displaystyle{ \{x: Q(x)=1\} }[/math] of problems in P, but rather the solution spaces [math]\displaystyle{ \{ y: R(x,y)=1\} }[/math] to instances of satisfiability problems "Given x, does there exist y for which R(x,y)=1" which are in P (and moreover, that the same should hold even when some partial assignment s of y has already been fixed). However, one can extend Gowers' objection to this case also. For instance, let [math]\displaystyle{ R: \{0,1\}^n \times \{0,1\}^{n} \to \{0,1\} }[/math] be a pseudorandom circuit (so x has n bits and y has n bits). Then for n large enough, the satisfiability problem should always have an affirmative answer (and in particular is trivially in P) provided that at least [math]\displaystyle{ 100 \log n }[/math] of the bits of y are left unassigned (this is basically because [math]\displaystyle{ \sum_n 2^{-2^{100 \log n}} 2^{O(n)} \lt \infty }[/math]), and the remaining cases when there are at most [math]\displaystyle{ 100 \log n }[/math] bits to assign can be verified by brute force. On the other hand the solution spaces [math]\displaystyle{ \{ y: R(x,y)=1\} }[/math] are still indistinguishable from random subsets of [math]\displaystyle{ \{0,1\}^n }[/math].

Algebrization

See Aaronson and Widgerson, "Algebrization: A New Barrier in Complexity Theory" ACM Transactions on Computation Theory (2009).

The paper is all about the local properties of a specific NP-complete problem (k-SAT), and for that reason, I don't think relativization is relevant. Personally, I'm more interested in why the argument makes essential use of uniformity (which is apparently why it's supposed to avoid Razborov-Rudich). (Scott Aaronson)

Average to Worst-case?

A possible new barrier implied by the discussion here, framed by Terry Tao:

If nothing else, this whole experience has highlighted a “philosophical” barrier to P != NP which is distinct from the three “hard” barriers of relativisation, natural proofs, and algebraisation, namely the difficulty in using average-case (or “global”) behaviour to separate worst-case complexity, due to the existence of basic problems (e.g. k-SAT and k-XORSAT) which are expected to have similar average case behaviour in many ways, but completely different worst case behaviour. (I guess this difficulty was well known to the experts, but it is probably good to make it more explicit.)

Note that "average case behaviour" here refers to the structure of the solution space, as opposed to the difficulty of solving a random instance of the problem.

Followup by Ryan Williams:

It is a great idea to try to formally define this barrier and develop its properties. I think the “not necessary” part is pretty well-understood, thanks to Valiant-Vazirani. But the “not sufficient” part, the part relevant to the current paper under discussion, still needs some more rigor behind it. As I related to Lenka Zdeborova, it is easy to construct, for every n, a 2-CNF formula on n variables which has many “clusters” of solutions, where each cluster has large hamming distance from each other, and within the cluster there are a lot of satisfying assignments. But one would like to say something stronger, e.g. “for any 3-CNF formula with solution space S, that space S can be very closely simulated by the solution space S’ for some CSP instance variables that is polytime solvable”.

See also the previous section on issues with random k-SAT for closely related points.

Terminology

Online reactions

Theory blogs

Media and aggregators

8th August

9th August

10th August

11th August

12th August

13th August

Real-time searches

Other


Additions to the above list of links are of course very welcome.

Timeline

Bibliography

Other links

Further reading

Given the current interest in the subject matters discussed on this page, it would be good to start collecting a list of references where people can learn more about such topics. Please add liberally to the list below.

  • There are many other complexity classes besides P and NP. See the Complexity Zoo
Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Deolalikar_P_vs_NP_paper&oldid=3568"