hi all more timely spring cleaning out my mountains of link piles. P vs NP has been a big topic in this blog but have pulled back on it somewhat myself to chase Collatz circles (surely equally impossible but still yet lower hanging fruit? does that make any “zen” sense?). but am always tracking it near at hand.

within the last year there have been a few notable blogs by leaders on the value of P vs NP proof attempts. RJLipton, Fortnow, Trevisan (a trifecta completed recently & partially triggering this post). there was also an archiv paper by undergraduate students of Hemaspaandra. usually there is a policy of “omerta”-like silence on these attempts. so its quite remarkable that these experts/ authorities are engaging with and/ or defending the efforts to some degree.

have been studying P vs NP attempts since the early 2000s or so *(“intermittently”!)*. think they have *some* “)(” value but with great qualification on that. experts are busy and should never feel obligated to pay any attention. but encouraging others to attempt to respond in some way seems positive & minimally risky.

what truly amazes me are how many of these “attempts” (actually claims) that are by Phds, some of them from very elite schools worldwide. now one would not be surprised that attempts by undergraduates or people who have not even attended college would be bogus and not have much value. but when very highly trained Phds come up with unintelligible papers, it would seem to call into question our educational system to “some degree”. & so far no comment by any experts on *that* angle…

clearly not all proofs are born equal & its not entirely helpful to pretend its a nearly uniform/ monolithic heap, its a sort of scientific equivalent of a publishers “slush pile”…. they have a wide range of contents/ mechanics; some are nearly unintelligible, others are easily “disposed of” (to use scientific/ academic vernacular) by undergraduates as in the Hemaspaandra case.**[a3]** or in the Trevisan case he is reviewing a very advanced attack by Peng.**[a2]**

so obama’s now-semilegendary quip about “junior varsity” (in a much different context) might come to mind here. do stunning “upsets” happen in scientific fields somewhat similar to athletic fields? yes! but they are exceedingly rare. the only one from recent experience anything remotely like that is Zhangs twin prime proof, but ofc he is a Phd!

so there is nothing to report as far as new P vs NP proofs, its the same old batch/ pile of half-baked ideas (or less! to put it politely!) around for many years. (as police say at an accident scene, *“nothing to see here folks, move along.”*) but top experts engaging with to some small )( degree is something of a notable shift/ even near-breakthrough. my personal appreciation to those who can find some kind of intermediate comensurate response/ compromise/ nuance between the extremes of cold silence and mania/ derision/ ridicule/ banning/ blocking.**[b13][a10]** this all also has a major connection to Open Science. & how a scientific community deals with its collective achilles heel/ embarrassments is a real window into/ test of its collective personality. or more specifically the “shadow side”.

alas the experts refer to the P vs NP problem or other famous timesucking open problems facetiously/ jokingly sometimes as a “disease” or “virus” (RJlipton, Gowers, Tao, etc) and this is partly in reference to all the bogus proof attempts. the $1M claymath prize doesnt exactly always help matters there. this idea of a half-joking derogatory term for a famous open problem seems to originate in the 1977 paper on Graph Isomorphism Disease by Read/ Corneil. am willing to laugh some and the term accurately captures some of the negative feelings (futility, depression etc) experts sometimes feel wrt them but also dont exactly like this kind of PR for the field. how would mathematicians feel about referring to eg the Riemann hypothesis as a *“disease”? what goes around comes around!*

P vs NP proof proliferation can be seen as a sort of test of “collective intelligence”. individually humans can be quite brilliant. collectively, humans have trouble channelling that individual intelligence, or lack of it. the community has indeed occasionally engaged in a serious way with these proofs eg the semifamous Deolalikar proof which triggered massive online community attn/ reaction by topnotch scientists eg RJLipton, & even Cook himself (essentially one of the 1st ever *viral scientific paper(s)!*), and thats something to be proud of… but in now-receding rear-view-mirror retrospect it now looks like a one-of-a-kind event so far. clearly, as everyone in the community is well/ long aware, *the lack of a P vs NP proof so far has absolutely nothing to do with lack of (expert) reviewers* (the old metaphor of *“pushing on a string”* comes to mind here)—but, on the other hand (now weighing in here also!)…

speaking of “defense”… now briefly )( playing devils advocate… 😈

if one looks at the semifamous woeginger list

[a6]there is quite a bit ofbrainpowerrepresented here, literally dozens of different authors.😮 😄 … hey! you there in the back! try not to snicker/ laugh/ scoff, too loud, at that assertion, & devalue real work! of course, “close only counts in horseshoes and hand grenades,” and Paulis timeless notorious deadly caustic phrase not even wrong ringingly echoes/ reverberates here, but …

lets be honest, it takes

major intellectual effortto write papers, incl citations, some with graphs, many with good latex skills and grasps of the basics that all might be beyond some undergraduates! seem to have met quite a few grad students online who have still not written any paper(s) at all! which makes one wonder, similarly to “love”, is it better to have written an erroneous/ false paper than to have never written one at all? my personal answer, quite possibly!& lets not forget that very few, maybe virtually no undergraduate programs whatsoever involve mandatory independent scientific research and/ or writing scientific papers, excluding honors classes/ theses. yes, there do exist “research experience for undergraduate” REU type programs in the US & elsewhere, but only a tiny fraction of gifted/ ambitious students are involved in them …

wrt the illustrious Woeginger “candidates”, each works (almost?) entirely independently of all the others, separate islands with no intercommunication/ interaction/ collaboration. isnt there something more that can be done here? for *years* have thought: why not get a P vs NP online/ cyber attack study group/ club together? there are very open stackexchange chat rooms for this type of thing. oh, one can only conclude, maybe writing a P vs NP proof is *easy* compared to actual *(live!)* *open science collaboration on the internet* which is apparently much more challenging, maybe more like rocket science! hey, they wrote the papers, what more can you ask? so they are all presumably just hanging around their phones waiting for the ClayMath committee to call… *any minute now!* 😎 😡 🙄

(oh hey speaking of devaluation & veering into politically incorrect territory… along the lines of cheap shots/ tasteless jokes… *caveat,* skip this paragraph if you have delicate sensibilities… has anyone noticed how many authors of different particular nationalities are on the Woeginger list? based on superficial analysis of their names? its a sort of ignominious reverse international Math Olympics competition! where do the most originate? US? Russia? China? how about this for a wild conjecture, could there possibly be any *(inverse)* correlation with educational quality in those countries, or even national personalities? and psychology plays some role here… naiveté? blind ambition? denial? narcissism?) 😮 😦 😳

ok, now off the comedy stage/ soapbox! meanwhile, elsewhere… stackexchange is a great radar/ barometer of the cyber zeitgeist and intermittent Q/A show up on the subject there & a selection of recent ones are included below. also in a small breakthrough, a meta post on the very elite/ rigorous cstheory site at least asking for a moratorium on reference to “cranks” is predictably controversial but currently has an overall positive vote (now +10v -6v = +4 total). a small )( victory. in math as everywhere else, “choose your battles wisely.”

**a. p vs np**

- 1. Computational Complexity: Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP? / Fortnow blog
- 2. Two recent papers by Cui Peng / Trevisan blog
- 3. [1504.06890] A Refutation of the Clique-Based P=NP Proofs of LaPlante and Tamta-Pande-Dhami
- 4. In Praise Of P=NP Proofs | Gödel’s Lost Letter and P=NP
- 5. Jun Fukuyama’s P≠NP Page | Hacker News
- 6. P-versus-NP page
- 7. Shtetl-Optimized » Blog Archive » Eight Signs A Claimed P≠NP Proof Is Wrong
- 8. Shtetl-Optimized » Blog Archive » Ten Signs a Claimed Mathematical Breakthrough is Wrong
- 9. outline for a NP vs P/poly proof based on monotone circuits, hypergraphs, factoring, and slice functions / TMachine blog
- 10. On Resolving the P vs NP Problem; or, on checking claims of resolving famous open problems / Goldreich

**b. stackexchange**

- 1. logic – Solving P vs NP with computer – Mathematics Stack Exchange
- 2. cc.complexity theory – Why is P vs. NP so hard? – Theoretical Computer Science Stack Exchange
- 3. open problem – How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich? – MathOverflow
- 4. soft question – Analogues of P vs. NP in the history of mathematics – MathOverflow
- 5. How to ask P vs NP questions without getting closed? – Computer Science Meta Stack Exchange
- 6. complexity theory – In basic terms, what is the definition of P, NP, NP-Complete, and NP-Hard? – Computer Science Stack Exchange
- 7. cc.complexity theory – Are runtime bounds in P decidable? (answer: no) – Theoretical Computer Science Stack Exchange
- 8. soft question – Analogues of P vs. NP in the history of mathematics – MathOverflow
- 9. cc.complexity theory – Statements that imply $\mathbf{P}\neq \mathbf{NP}$ – Theoretical Computer Science Stack Exchange
- 10. complexity theory – A paper argumenting that P might be equal to NP – Computer Science Stack Exchange
- 11. Is there any way to make a question about a P=NP “proof” on topic? – Theoretical Computer Science Meta Stack Exchange
- 12. Stop using the word “crank” on CStheory.se – Theoretical Computer Science Meta Stack Exchange
- 13. Is it ok to ask about the correctness of preprints on crank-friendly topics? cstheory.se

gsgsso, what’s your current subjective, informative estimate of the probability

that P=NP , or that P=?NP will be proved in [insert a timeframe]

I think that one or 2 or more numbers better sum up things and are more

informative than words. I wished (other) experts would also give their

probablity-estimate-numbers

(maybe I said that before … I forgot. I had that expert-probability-estimate

discussion wrt. H5N1 influenza-pandemic , (why I left math towards health))

gs

vznvznPost authorhi, thx for attn, speaking of “leading authorities”, gasarch has done 2 10yr polls, last one here and it includes estimates of when it will be proven by experts. my thinking is, generally along the same lines, & am “cautiously optimistic” P!=NP will be proved in my lifetime. 😐

Phillip SomervilleBeyond the false glitter of ‘fools gold’, ever so rarely, the greatest nuggets are quite literally found in the ruts of the road well traveled… so the legend goes.

http://en.wikipedia.org/wiki/Welcome_Stranger