This one may merit a summary, since there are a few subtleties. So, here goes. Background: Ever since Goedel, we know that in any given system for doing mathem

This one may merit a summary, since there are a few subtleties. So, here goes. Background: Ever since Goedel, we know that in any given system for doing mathematics some statements are neither provable nor refutable. So, if after much effort mathematicians fail to find either a proof or a disproof for some conjecture, it's natural to wonder whether perhaps that's because neither exists. In some cases, an undecidability result of this kind would be pretty much equivalent to an actual decision. For instance: Goldbach's conjecture says "every even number >= 4 is the sum of two prime numbers". If this is undecidable then, in particular, I can't write down an explicit counterexample, so it might as well be true. OK, so what about P=NP? Well, what David and Halevi have done is to show something a bit like the following: "If 'P=NP' is not decidable using the axioms of Peano arithmetic, then any family of decision problems that's in NP is 'almost in P'". But there are some fiddly details that might matter. Detail #1: it's not actually "is not decidable", it's "is provably not decidable". The distinction between these two is important to anyone who's interested in this stuff in the first place. Detail #2: it's not even "is provably not decidable", it's "is provably not decidable, where the undecidability proof is of a particular kind". They claim that "any known technique for proving independence from sufficiently strong theories of statements that are neither self-referential nor inherently proof-theoretic" is of this kind. Since the whole field of independence proofs got started when Goedel worked out how to make things "self-referential" that on the face of it look like completely the wrong kind of thing to sustain self-reference, I can't help but be a bit unimpressed by this. Detail #3: What they mean by "almost in P" is this: there are arbitrarily long intervals of arbitrarily large numbers such that any problem whose size lies in one of these intervals can be solved in almost-polynomial time -- i.e., O(n^f(n)) where f grows very, very slowly, in particular more slowly than log log ... log n with any number of "log"s.