norbert blum P vs NP attack goes CYBER-SCIENCE-VIRAL!

⭐ 💡 ❗ 😀 😎 ❤ hi all! want to write a lot on this, have all kinds of impressions and things to say on one of my favorite topics in the world for 2½ decades now and which this blog is partly dedicated to, but am starting out by just collecting some links vacuumed up mostly today for others to check out, the top locations for commentary. unf there is not really a key/ central place so far where all the action is happening. will be adding to this post as time goes on. its very hard to figure out when to time a post wrt very fast moving developments like this, but my trigger just hit mostly right after RJLipton[a10] blogged about it. oh yeah, that comment by gowers that “I think it may reach the level where the experts feel that it needs to be checked” is highly triggering for me too (referring ofc to himself in 3rd person, maybe being more than a bit )( coy about this— doncha just love hardcore mathematicians! which reminds me of the joke about shoelaces…) … oh and then theres also fortnow who literally wrote the book on it! (oh yeah wrt that theres this by RJL too!) 😛

it looks like the Norbert Blum paper[a14][a15] basically went “pop/ scientific viral” today or so probably after mentions on Reddit[a8][a9] and Hacker News.[a11] of the experts Trevisan[a1] was the first to wager a reaction along with some curious onlookers like Baez[a2] and verging-on-jester-or-gadfly-or-even-troll Motl[a5] who along with some mild conspiracy theory about CS research(ers) (lol!) says, wrt the #1 top problem in TCS…

Except that unlike the case of string theory, there exists absolutely no rational evidence that there exists something stunning waiting to be discovered.

@#$% 😡 👿 ❗ whoa, fighting words and/ or near-sacrilege there! excuse me, what is “stunning” is that the problem with $1M prize over 1½ decade has eluded/ stymied/ thwarted the worlds greatest scientific minds for almost ½ century now! and the proof either way, in whatever shape or form, will be assuredly stunning to anyone who isnt jaded or a nihilist! hey physics bozo! think of a great experiment that guaranteed leads to an extraordinary answer either way! arent there any examples like that in your field anyway? or is maybe someone looking a little envious over there? or out of the loop or maybe dont even know how to flirt at all? :mrgreen:

the TCS stackexchange post by a n00b newbie (who didnt know enough to not ask! hows that for “zen beginners mind”?) is now up to 136-4 votes and 28K hits (thursday eve 8/17).[a3] (joy that the lame heavyhanded/ constricting/ dictatorial policy of the self-appointed cyber spoilsports and partypoopers also long criticized here in this blog, is overruled by striking mass opposition!) that post slipped my radar for a few days! found the paper on the 1st day (monday this wk) but thought it might stay “unviral” (you know, like those killer viruses locked in the… thawing… arctic, right?) based esp on the last Hauptmann attempt.[a12][a13]

discovered the big commotion today via reddit myself and spent excited hours poking through sites! but my hits on the Hauptmann blog post had been creeping/ climbing up massively all week, merely from google searches (many from germany), and figured it was due to questions on the Blum attempt. turns out theyre both profs at the same university! (Bonn/ Germany) pardon me but wtf?!?… some kind of story there eh? are any reporters listening?

cyberspace is such a joy sometimes, in my quasi-bipolar days, mostly-sometimes seemingly very flat for days, weeks, months, even years at a time, this is a massive manic spike for me… the adrenalin is flowing! didnt sleep as well this week! there is so much cybersynchronicity to this, must admit, its a very rare event, am myself (and defensively, some others are too) having a bit of a mini-cyber-orgasm so far… 💡 😮 o_O 🙄 ❗

why is this such a big deal for me? have been blogging for ~½ decade now on the problem, but also the particular attack direction: monotone circuit theory, even sketching out some similar ideas in one of the earliest posts on this blog. this general area seems to me to deserve much more scientific/ professional attention than its getting. some of that may be due to its “alpha male” Razborov who blazed the trail—then later shortly thereafter looked at it skeptically with a cold-water-splash-in-face no-go theorem. has anyone read that no-go theorem? looked up the paper years ago and admittedly find it utterly impenetrable. (speaking of my own “suspicions,” think maybe the citations vs ppl whove read/ understand it is way out of whack on that one!) but maybe Razborovs own giant/ sterling reputation/ instincts were enough to cause mass skepticism…?

it does seem to me there is unexplored territory, terra incognita somewhere around the idea of sunflowers and cnf-dnf approximator constructions. my own dreamy intuition has sometimes been that maybe P vs NP might reduce to some sunflower bound problem. sunflowers play a central role in these proofs, but Blum has nothing to say about them in particular, which admittedly (a small looking askance at the parade) is a kind of a generic red flag for me so far. also feel like he hasnt given a nice sound/bite overview of the basic approach anywhere in the document, but such a thing is not mandatory.

but mostly am very enthused ecstatic that multiple experts are engaging with this proof in cyberspace, which imho is a little too rare—you know, that tricky-but-rewarding stuff known as “teamwork” or “collaboration”. there are several P vs NP attempts on the woeginger list by fellow Phds (out of the more than 100 total now by “unwashed masses aka riff raff”) and its always kind of surprised me how fellow Phds dont really take them at all seriously or engage with them whatsoever. which makes the words “professional courtesy” sounds a bit )( like a misnomer or worse yet, an oxymoron. 😦 😳

its now been 7 long years since the last viral P vs NP attack attempt by my count, namely the Deolalikar proof, and think thats a bit )( of a shame. am not asking for every attempt to go viral, am just asking fellow scientists to take some time on the serious attempts. it really does seem like in this case the scientists didnt pay a lot of attention until mass popular attention mounted, although maybe thats just my bias; the virality all happened so far in just a few days and some case can be made the scientists were “on it” from the beginning eg as with Trevisan. honestly in this case it does look like professional/ amateur/ curious onlooker attention all mounted nearly in synchrony.

❤ would luv to finish off on that high note, but heres a maybe even higher note. RJLipton writes:[a10]

But this leads us to a larger point. Both of us are involved right now with painstaking constructions involving quantum circuits and products of permutations that we are programming (in Python). Pages 27–28 of Blum’s paper give a construction that can be programmed. If this is done enough to crank out some examples, then we may verify that potential flaws crop up or alternatively bolster confidence in junctures of the proof so as to focus on others first. This ability is one way we are now empowered to sharpen “fuzzy edges” of our science.

😮 huh? holy cow!?! — or goring one! — did you say, “computer experiments”? dudes, are you crazy? thought you cerebral ivory tower comp scientists never get your hands dirty do you? anyway though its definitely music to my ears! but whoever thought that P vs NP would have anything to do with actual applied software/ (running!) computer code anyway? (which reminds me of this amusing Dijkstrian gem)o_O 😎 😀

(fri 8/18)

  • idolvon seems to have refuted it on the SE post finding/ zeroing in the specific problematic construction/ misunderstanding.
  • also the grandmaster razborov himself weighs in “2ndhand” with a refutation noted in Trevisan’s blog and comments, citing Tardos.
  • elsewhere, 1st MSM coverage! the Register writes article and emailed Blum who replied “its too early for such a question” of whether anyones confirmed it.
  • ❗ 😮 the stackexchange TCS post is up to an astounding/ record breaking ~50Khits.

“proving” theres a real/ strong worldwide/ popular thirst for seeing 1stclass science in play-by-play action/ progress in cyberspace. maybe all the cyber-shy/ introvert scientists might think about reevaluating their reservations/ trepidations on that. or maybe the whole spectacle just reinforces confirmation bias about that, lol! is it now 50K rubberneckers right at the scene of a STEM accident/ crash? is it the $1M prize thats turning TCS into an occasionally spectator sport? o_O


  • aaronson weighs in on the incorrect proof, also mocks “mubos lotl”, and registers
  • stackexchange post up to 77K hits. oh and Blum is giving a public talk on aug 29th (*) as announced on reddit— guess he feels the airplane is still in the air and hasnt been shot down yet so to speak! (see reddit comments for some skeptical views… does he even read the internet?)
  • inspired by all this, wrote up some of my own (vaguely similar) ideas that have been bouncing/ jangling/ rattling in my head for awhile… as documented years ago/ over the years on this blog, do think blum is sniffing in the right direction/ on the right track, in an area that has otherwise long been “given up for dead” by other experts/ authorities!

(8/31) *

  • ❗ ❓ 😮 😳 o_O site administrator deleted the lecture announcement page without further info. did the talk happen? was it cancelled? dont have further info yet. really wish there was a video if it did.
  • elsewhere from the cs blogging grapevine, namely David Eppstein, heard about this new wikipedia entry for the critical/ remarkable Tardos function used in the disproof.
  • Fortnow weighs in on proof citing Tardos function.
  • cstheory post now up to 90K hits/ 206-4=202 votes.
  • was able to generate/ have a bit )( of discussion with new users/ faces on long est theory salon chat room but alas looks unsustainable & no new regulars/ recruits out of this epic “flash in the pan”. (oh well! easy come easy go!™) 😦 😐
  • lol wrote all those items before hitting reddit, maybe better change that next time! reddit math and compsci threads have comment talk was cancelled, cite that hes admitted the proof is flawed on the arxiv summary page & updated paper on 30th. “The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage”

(9/1) one of those bizarre cyber moments… got record daily hits spike on this blog yesterday from the announced retraction of the proof and apparently mainly from random surfer curiosity over some snarky comments about the blog on a reddit thread.[1][2] wow, thx reddit snarks! guess theres no such thing as bad publicity as long as they get the url right! & ofc gotta cite it because its more comments in a few hrs than this blog gets in a few months! ❗ 😀 😛

a. nblum

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s