Links with little comment (P != NP)

Updated: Two links to R. J. Lipton’s blog with possible flaws — first, an explanation of a type error (really, very readable, and recommended); and second, a serious threat (note that, altough the link does not include it, the title of the post has a question mark at the end!).

Then, a personal note — I do not know Vinay Deolalikar, but I hope he has quite a bit of internal fortitude.  I am led to believe that the discussion has been non-personal, and even, perhaps, supportive, but to have your ideas attacked is not easy, even when couched in constructive-criticism form.  I read in one set of comments a back-and-forth which indicated some derision for HP Labs (not exactly, but a definite negative vibe, and clearly I’m not alone in that perception [see the comments in the 2nd post, about 11:24 PM August 12 — sorry I couldn’t link to it…]).

FWIW, here is the wiki discussion of the proof.

(Someone is going to ask: what is P vs. NP? And I don’t have a good answer; but here is a hint at why it matters: certain types of problems, which are considered very difficult, or even insoluble, would begin to yield answers — the most common example is cryptography: codes to protect privacy could, in theory, be breakable!  Wolfram gives a somewhat technical intro, including a link to the first episode of NUMB3RS [spoiler alert].

Thanks to MIT for providing a quick answer for the layman.)

Since I’m not even close to competent to comment on the proposed proof, which is in the news, I’m just going to link to a couple of items (which you could find as easily thru the same article), with a few, and only a few comments: Scott Aaronson, of MIT, is doubtful in this Technology Review article.  (he also wrote  a somewhat humorous, but very readable post about 10 ‘signs’ a proof is probably wrong.)

For a technical discussion of [four] “problems” (which may or may not be soluble), see Lipton and Regan.  (The 2nd post on this blog, by “Dick Lipton, a Professor of Computer Science at Georgia Tech” — the first is here.  [I think that blog is one I should follow for updates, regularly!]

Now I need to figure out the acronyms “SAT” and “2SAT,” “3SAT,” and “k-SAT,” for starters…  [ed. found that!]

1st update: I’m going to have to give Wikipedia its due, especially after some reading like this.

I’m going to publish this AS-IS, and update when I know more (or someone has questions…)