Update 26\/08\/2017:<\/b><\/span> Comments should now be working again; comments are now coming through to the moderated view in the blog’s control panel, so if they don’t show up immediately it might just be awaiting moderation. Thanks for your patience.<\/p>\n Last weekend, I was in Columbia, South Carolina, for a workshop to honor the 60th birthday of Stuart Kurtz<\/a>, theoretical computer scientist at the University of Chicago. I gave a talk about how work Kurtz was involved in from the 1990s—for example, on defining the complexity class GapP<\/a>, and constructing oracles that satisfy conflicting requirements simultaneously—plays a major role in modern research on quantum computational supremacy: as an example, my recent paper with Lijie Chen<\/a>. (Except, what a terrible week to be discussing the paths to supremacy! I promise there are no tiki torches involved, only much weaker photon sources.)<\/p>\n Coincidentally, I don’t know if you read anything about this on social media, but there was this total solar eclipse that passed right over Columbia at the end of the conference.<\/p>\n I’d always wondered why some people travel to remote corners of the earth to catch these. So the sky gets dark for two minutes, and then it gets light again, in a way that’s been completely understood and predictable for centuries?<\/p>\n Having seen it, I can now tell you the deal, if you missed it and prefer to read about it here rather than 10500<\/sup> other places online. At risk of stating the obvious: it’s not the dark sky; it’s the sun’s corona visible around the moon. Ironically, it’s only when the sun’s blotted out that you can actually look<\/em> at the sun, at all the weird stuff going on around its disk.<\/p>\n OK, but totality is “only” to eclipses as orgasms are to sex. There’s also the whole social experience of standing around outside with friends for an hour as the moon gradually takes a bigger bite out of the sun, staring up from time to time with eclipse-glasses to check its progress—and then everyone breaking into applause as the sky finally goes mostly dark, and you can look at the corona with the naked eye. And then, if you like, standing around for another<\/em> hour as the moon gradually exits the other way. (If you’re outside the path of totality, this standing around and checking with eclipse-glasses is the whole<\/em> experience.)<\/p>\n One cool thing is that, a little before and after totality, shadows on the ground have little crescents in them, as if the eclipse is imprinting its “logo” all over the earth.<\/p>\n For me, the biggest lesson the eclipse drove home was the logarithmic nature of perceived brightness<\/a> (see also Scott Alexander’s story<\/a>). Like, the sun can be more than 90% occluded, and yet it’s barely a shade darker outside. And you can still<\/em> only look up with glasses so dark that they blot out everything except<\/em> the sliver of sun, which still looks pretty much like the normal sun if you catch it out of the corner of your unaided eye. Only during totality, and a few minutes before and after, is the darkening obvious.<\/p>\n Another topic at the workshop, unsurprisingly, was the ongoing darkening of the United States. If it wasn’t obvious from my blog’s name, and if saying so explicitly will make any difference for anything, let the record state:<\/p>\n Shtetl-Optimized<\/em> condemns Nazis, as well as anyone who knowingly marches with Nazis or defends them as “fine people.”<\/strong><\/p>\n For a year, this blog has consistently described the now-president as a thug, liar, traitor, bully, sexual predator, madman, racist, and fraud, and has urged decent people everywhere to fight him by every peaceful and legal means available. But if there’s some form of condemnation that I accidentally missed, then after Charlottesville, and Trump’s unhinged quasi-defenses of violent neo-Nazis, and defenses of his previous defenses, etc.—please consider Shtetl-Optimized<\/em> to have condemned Trump that way also.<\/p>\n At least Charlottesville seems to have set local decisionmakers on an unstoppable course toward removing the country’s remaining Confederate statues—something I strongly supported back in May<\/a>, before it had become the fully thermonuclear issue that it is now. In an overnight operation, UT Austin has taken down its statues<\/a> of Robert E. Lee, Albert Johnston, John Reagan, and Stephen Hogg. (I confess, the postmaster general<\/i> of the Confederacy wouldn’t have been my #1 priority for removal. And, genuine question: what did Texas governor Stephen Hogg<\/a> do that was so awful for his time, besides naming his daughter Ima Hogg<\/a>?)<\/p>\n A final thing to talk about—yeah, we can’t avoid it—is Norbert Blum’s claimed proof of P\u2260NP<\/a>. I suppose I should be gratified that, after my last post, there were commenters who said, “OK, but enough about gender politics—what about P vs. NP?” Here’s what I wrote on Tuesday the 15th:<\/p>\n To everyone who keeps asking me about the \u201cnew\u201d P\u2260NP proof: I\u2019d again bet $200,000 that the paper won\u2019t stand, except that the last time I tried that, it didn\u2019t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn\u2019t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.<\/p>\n Many people misunderstood me to be saying that I’d again<\/a> bet $200,000, even though the sentence said the exact opposite. Maybe I should’ve said: I’m searching in vain for the right way to teach the nerd world to get less excited about these claims, to have the same reaction that the experts do, which is ‘oh boy, not another one’—which doesn’t mean that you know the error, or even that there is an error, but just means that you know the history.<\/em><\/p>\n Speaking of which, some friends and I recently had an awesome idea. Just today, I registered the domain name haspvsnpbeensolved.com<\/strong>. I’d like to set this up with a form that lets you type in the URL of a paper claiming to resolve the P vs. NP problem. The site will then take 30 seconds or so to process the paper—with a status bar, progress updates, etc.—before finally rendering a verdict about the paper’s correctness. Do any readers volunteer to help me create this? Don’t worry, I’ll supply the secret algorithm to decide correctness, and will personally vouch for that algorithm for as long as the site remains live.<\/p>\n I have nothing bad to say about Norbert Blum, who made important contributions including the 3n circuit size lower bound<\/a> for an explicit Boolean function—something that stood until very recently as the world record—and whose P\u2260NP paper was lucidly written, passing many of the most obvious checks<\/a>. And I received a bit of criticism for my “dismissive” stance. Apparently<\/em>, some right-wing former string theorist who I no longer read, whose name rhymes with Mubos Lotl, even accused me of being a conformist left-wing ideologue, driven to ignore Blum’s proof by an irrational conviction that any P\u2260NP proof will necessarily be so difficult that it will need to “await the Second Coming of Christ.” Luca Trevisan’s reaction<\/a> to that is worth quoting:<\/p>\n I agree with [Mubos Lotl] that the second coming of Jesus Christ is not a necessary condition for a correct proof that P is different from NP. I am keeping an open mind as to whether it is a sufficient condition.<\/p>\n On reflection, though, Mubos has a point: all of us, including me, should keep an open mind. Maybe P\u2260NP (or P=NP!) is vastly easier to prove than most experts think, and is susceptible to a “fool’s mate.”<\/p>\n That being the case, it’s only intellectual honesty that compels me to report that, by about Friday of last week—i.e., exactly on my predicted schedule—a clear consensus had developed among experts that Blum’s P\u2260NP proof was irreparably flawed, and the consensus has stood since that time.<\/p>\n I’ve often wished that, even just for an hour or two, I could be free from this terrifying burden that I’ve carried around since childhood: the burden of having the right instincts about virtually everything. Trust me, this “gift” is a lot less useful than it sounds, especially when reality so often contradicts<\/a> what’s popular or expedient to say.<\/p>\n The background to Blum’s attempt, the counterexample that shows the proof has to fail somewhere<\/em>, and the specifics of what appears to go wrong have already been covered at length elsewhere: see especially Luca’s post<\/a>, Dick Lipton’s post<\/a>, John Baez’s post<\/a>, and the CS Theory StackExchange thread<\/a>.<\/p>\n Very briefly, though: Blum claims to generalize some of the most celebrated complexity results of the 1980s—namely, superpolynomial lower bounds on the sizes of monotone <\/em>circuits, which consist entirely of Boolean AND and OR gates—so that they also work for general<\/em> (non-monotone) circuits, consisting of AND, OR, and NOT gates. Everyone agrees that, if this succeeded, it would imply P\u2260NP.<\/p>\n Alas, another big discovery from the 1980s was that there are monotone Boolean functions (like Perfect Matching) that require superpolynomial-size monotone circuits, even though they have polynomial-size non-monotone circuits. Why is that such a bummer? Because it means our techniques for proving monotone circuit lower bounds can’t possibly work in as much generality as one might’ve na\u00efvely hoped: if they did, they’d imply not merely that P doesn’t contain NP, but also that P doesn’t contain itself.<\/p>\n Blum was aware of all this, and gave arguments as to why his approach evades the Matching counterexample. The trouble is, there’s another<\/em> counterexample, which Blum doesn’t address, called Tardos’s function<\/a>. This is a weird creature: it’s obtained by starting with a graph invariant called the Lov\u00e1sz theta function<\/a>, then looking at a polynomial-time approximation scheme for the theta function, and finally rounding the output of that PTAS to get a monotone function. But whatever: in constructing this function<\/a>, Tardos achieved her goal, which was to produce a monotone function that all<\/em> known lower bound techniques for monotone circuits work perfectly fine for, but which is nevertheless in P (i.e., has polynomial-size non-monotone circuits). In particular, if Blum’s proof worked, then it would also work for Tardos’s function, and that gives us a contradiction.<\/p>\n Of course, this merely tells us that Blum’s proof must have<\/em> one or more mistakes; it doesn’t pinpoint where they are. But the latter question has now been addressed as well. On CS StackExchange, an anonymous commenter who goes variously by “idolvon” and “vloodin” provides a detailed analysis<\/a> of the proof of Blum’s crucial Theorem 6. I haven’t gone through every step myself, and there might be more to say about the matter than “vloodin” has, but several experts who are at once smarter, more knowledgeable, more cautious, and more publicity-shy than me have confirmed for me that vloodin correctly identified the erroneous region.<\/p>\n To those who wonder what gave me the confidence to call this immediately, without working through the details: besides the Cassandra-like burden that I was born with, I can explain something that might be helpful. When Razborov achieved his superpolynomial monotone lower bounds in the 1980s, there was a brief surge of excitement: how far away could a P\u2260NP proof possibly be? But then people, including Razborov himself, understood much more deeply what was going on—an understanding that was reflected in the theorems they proved, but also wasn’t completely captured by those theorems.<\/p>\n What was going on was this: monotone circuits are an interesting and nontrivial computational model. Indeed for certain Boolean functions, such as the “slice functions,”<\/a> they’re every bit as powerful as general circuits. However, insofar as it’s possible to prove superpolynomial lower bounds on monotone circuit size<\/em>, it’s possible only because monotone circuits are ridiculously less expressive than general Boolean circuits for the problems in question<\/em>. E.g., it’s possible only because monotone circuits aren’t expressing pseudorandom functions, and therefore aren’t engaging the natural proofs barrier<\/a> or most of the other terrifying beasts that we’re up against.<\/p>\n So what can we say about the prospect that a minor tweak to the monotone circuit lower bound techniques from the 1980s would yield P\u2260NP? If, like Mubos Lotl, you took the view that discrete math and theory of computation are just a mess of disconnected, random statements, then such a prospect would seem as likely to you as not. But if you’re armed with the understanding above, then this possibility is a lot like the possibility that the OPERA experiment discovered superluminal neutrinos<\/a>: no, not a logical impossibility, but something that’s safe to bet against at 10,000:1 odds.<\/p>\n
\n![](\"https:\/\/scottaaronson.blog\/shadows-sm.jpg\")
<\/p>\n
\n
\n