{"id":1720,"date":"2014-03-07T04:16:08","date_gmt":"2014-03-07T09:16:08","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1720"},"modified":"2016-12-10T04:24:16","modified_gmt":"2016-12-10T09:24:16","slug":"the-scientific-case-for-p%e2%89%a0np","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1720","title":{"rendered":"The Scientific Case for P\u2260NP"},"content":{"rendered":"

Out there in the wider world—OK, OK, among Lubo\u0161 Motl<\/a>, and a few others who comment on this blog—there appears to be a widespread opinion that P\u2260NP is just “a fashionable dogma of the so-called experts,” something that’s no more likely to be true than false. \u00a0The doubters can even point to at least one accomplished complexity theorist, Dick Lipton, who publicly advocates agnosticism<\/a> about whether P=NP.<\/p>\n

Of course, not all the doubters reach their doubts the same way. \u00a0For Lipton, the thinking is probably something like: as scientists, we should be rigorously open-minded, and constantly question even the most fundamental hypotheses of our field<\/em>. \u00a0For the outsiders, the thinking is more like: computer scientists are just not very smart—certainly not as smart as real scientists—so the fact that they consider something a “fundamental hypothesis” provides no information of value.<\/em><\/p>\n

Consider, for example, this comment<\/a> of Ignacio Mosqueira:<\/p>\n

If there is no proof that means that there is no reason a-priori to prefer your arguments over those [of] Lubos. Expertise is not enough. \u00a0And the fact that Lubos is difficult to deal with doesn\u2019t change that.<\/p>\n

In my response<\/a>, I wondered how broadly Ignacio would apply the principle “if there’s no proof, then there’s no reason to prefer any argument over any other one.” \u00a0For example, would he agree with the guy interviewed on Jon Stewart<\/a> who earnestly explained that, since there’s no proof that turning on the LHC will destroy the world, but also no proof that it won’t<\/em> destroy the world, the only rational inference is that there’s a 50% chance it will destroy the world? \u00a0(John Oliver’s deadpan response was classic: “I’m … not sure<\/em> that’s how probability works…”)<\/p>\n

In a lengthy reply<\/a>, Lubo\u0161\u00a0bites this bullet with relish and mustard. \u00a0In physics, he agrees, or even in “continuous mathematics that is more physics-wise,” it’s possible to have justified beliefs even without proof. \u00a0For example,\u00a0he admits to a 99.9% probability that the Riemann hypothesis is true. \u00a0But, he goes on, “partial evidence in discrete mathematics just cannot exist.” \u00a0Discrete math and computer science, you see, are so arbitrary, manmade, and haphazard that every question is independent of every other; no amount of experience can give anyone any idea which way the next<\/em> question will go.<\/p>\n

No, I’m not kidding. \u00a0That’s his argument.<\/p>\n

I couldn’t help wondering: what about number theory? \u00a0Aren’t the positive integers a “discrete” structure? \u00a0And isn’t the Riemann Hypothesis fundamentally about the distribution of primes? \u00a0Or does the Riemann Hypothesis get counted as an “honorary physics-wise continuous problem” because it can also<\/em> be stated analytically? \u00a0But then what about Goldbach’s Conjecture? \u00a0Is Lubo\u0161\u00a050\/50 on that one too? \u00a0Better yet, what about continuous, analytic problems that are closely related to P vs. NP? \u00a0For example, Valiant’s Conjecture<\/a> says you can’t linearly embed the permanent of an n\u00d7n matrix as the determinant of an m\u00d7m matrix, unless m\u2265exp(n). \u00a0Mulmuley and others have connected this “continuous cousin” of P\u2260NP to issues in algebraic geometry, representation theory, and even quantum groups and Langlands duality. \u00a0So, does that make it kosher? \u00a0The more I thought about the proposed distinction, the less sense it made to me.<\/p>\n

But enough of this. \u00a0In the rest of this post,\u00a0I want to explain why the odds that you should assign to P\u2260NP are more like 99% than they are like 50%. \u00a0This post supersedes my 2006 post<\/a> on the same topic, which I hereby retire. \u00a0While that post was mostly OK as far as it went, I now feel like I can do a much better job articulating the central point. \u00a0(And also, I made the serious mistake in 2006 of striving for literary eloquence and tongue-in-cheek humor. \u00a0That works great for readers who already know the issues inside-and-out, and just want to be amused. \u00a0Alas, it doesn’t work so well for readers who don’t<\/em>\u00a0know the issues, are extremely literal-minded, and just want ammunition to prove their starting assumption that I’m a doofus who doesn’t understand the basics of his own field.)<\/p>\n

So, OK, why should you believe P\u2260NP? \u00a0Here’s why:<\/p>\n

Because, like any other successful scientific hypothesis, the P\u2260NP\u00a0hypothesis has passed severe tests that it had no good reason to pass were it false.<\/strong><\/p>\n

What kind of tests am I talking about?<\/p>\n

By now, tens of thousands of problems have been proved to be NP-complete. \u00a0They range in character from theorem proving to graph coloring to airline scheduling to bin packing to protein folding to auction pricing to VLSI design to minimizing soap films to winning at Super Mario Bros. \u00a0Meanwhile, another cluster of tens of thousands of problems has been proved to lie in P (or BPP). \u00a0Those range from primality to matching to linear and semidefinite programming to edit distance to polynomial factoring to hundreds of approximation tasks. \u00a0Like the NP-complete problems, many of the P and BPP problems are also related to each other by a rich network of reductions. \u00a0(For example, countless other problems are in P “because” linear and semidefinite programming are.)<\/p>\n

So, if we were to draw a map of the complexity class NP<\/a>\u00a0 according to current knowledge<\/em>, what would it look like? \u00a0There’d be a huge, growing component of NP-complete problems, all connected to each other by an intricate network of reductions. \u00a0There’d be a second huge component of P problems, many of them again connected by reductions. \u00a0Then, much like with the map of the continental US, there’d be a sparser population in the middle: stuff like factoring, graph isomorphism, and Unique Games that for various reasons has thus far resisted assimilation onto either of the coasts.<\/p>\n

Of course, to prove P=NP, it would suffice to find a single<\/em> link—that is, a single polynomial-time equivalence—between any of the tens of thousands of problems on the P coast, and any of the tens of thousands on the NP-complete one. \u00a0In half a century, this hasn’t happened: even as they’ve both ballooned exponentially, the two giant regions have remained defiantly separate from each other. \u00a0But that’s not even the main point. \u00a0The main point is that, as people explore these two regions, again and again there are “close calls”<\/strong>: places where, if a single parameter had worked out differently, the two regions would have come together in a cataclysmic collision. \u00a0Yet every single time, it’s just a fake-out. \u00a0Again and again the two regions “touch,” and their border even traces out weird and jagged shapes. \u00a0But even in those border zones, not a single problem ever crosses from one region to the other. \u00a0It’s as if they’re kept on their respective sides by an invisible electric fence.<\/p>\n

As an example, consider the Set Cover problem: i.e., the problem, given a collection of subsets S1<\/sub>,…,Sm<\/sub>\u2286{1,…,n}, of finding as few subsets as possible whose union equals the whole set. \u00a0Chvatal showed in 1979 that a greedy algorithm can produce, in polynomial time, a collection of sets whose size is at most ln(n) times larger than the optimum size. \u00a0This raises an obvious question: can you do better? \u00a0What about 0.9ln(n)? \u00a0Alas, building on a long sequence of prior works in PCP theory, it was recently<\/a> shown<\/a>\u00a0that, if you could find a covering set at most (1-\u03b5)ln(n) times larger than the optimum one, then you’d be solving an NP-complete problem, and P would equal NP. \u00a0Notice that, conversely, if the hardness<\/em> result worked for ln(n) or anything above, then we’d also get P=NP. \u00a0So, why do the algorithm and the hardness result “happen to meet” at exactly ln(n), with neither one venturing the tiniest bit beyond? \u00a0Well, we might say,\u00a0ln(n) is where the invisible electric fence is for this problem.<\/p>\n

Want another example? \u00a0OK then, consider the “Boolean Max-k-CSP” problem: that is, the problem of setting n bits so as to satisfy the maximum number of constraints<\/em>, where each constraint can involve an arbitrary Boolean function on any k of the bits. \u00a0The best known approximation algorithm, based on semidefinite programming, is guaranteed to satisfy at least a 2k\/2k<\/sup> fraction of the constraints. \u00a0Can you guess where this is going? \u00a0Recently, Siu On Chan showed<\/a> that it’s NP-hard to satisfy even slightly<\/em> more than a 2k\/2k<\/sup>\u00a0fraction of constraints: if you can, then P=NP. \u00a0In this case the invisible electric fence sends off its shocks at 2k\/2k<\/sup>.<\/p>\n

I could multiply such examples endlessly—or at least, Dana (my source for such matters) could do so. \u00a0But there are also dozens of “weird coincidences” that involve running times rather than approximation ratios; and that strongly suggest, not only that P\u2260NP,\u00a0but that problems like 3SAT should require cn<\/sup> time for some constant c. \u00a0For a recent example—not even a particularly important one, but one that’s fresh in my memory—consider this paper<\/a> by myself, Dana, and Russell Impagliazzo. \u00a0A first thing we do in that paper is to give an approximation algorithm for a family of two-prover games called “free games.” \u00a0Our algorithm runs in quasipolynomial<\/em> time: \u00a0specifically, nO(log(n))<\/sup>. \u00a0A second thing we do is show how to reduce the NP-complete 3SAT problem to free games of size ~2O(\u221an)<\/sup>.<\/p>\n

Composing those two results, you get an algorithm for 3SAT whose overall running time is roughly<\/p>\n

$$ 2^{O( \\sqrt{n} \\log 2^{\\sqrt{n}}) } = 2^{O(n)}. $$<\/p>\n

Of course, this doesn’t improve on the trivial “try all possible solutions” algorithm. \u00a0But notice that, if our approximation algorithm for free games had been slightly<\/em> faster—say, nO(log log(n))<\/sup>—then we could’ve used it to solve 3SAT in $$ 2^{O(\\sqrt{n} \\log n)} $$ time. \u00a0Conversely, if our reduction from 3SAT had produced free games of size (say) $$ 2^{O(n^{1\/3})} $$ rather than 2O(\u221an)<\/sup>, then we could’ve used that<\/em> to solve 3SAT in $$ 2^{O(n^{2\/3})} $$ time.<\/p>\n

I should stress that these two results have completely different proofs: the approximation algorithm for free games “doesn’t know or care” about the existence of the reduction, nor does the reduction know or care about the algorithm. \u00a0Yet somehow, their respective parameters “conspire” so that 3SAT still needs cn<\/sup>\u00a0time. \u00a0And you see the same sort of thing over and over, no matter which problem domain you’re interested in. \u00a0These ubiquitous “coincidences” would be immediately explained if 3SAT actually did<\/em>\u00a0require\u00a0cn<\/sup>\u00a0time—i.e., if it had a “hard core” for which brute-force search was unavoidable, no matter which way you sliced things up. \u00a0If that’s not<\/em> true—i.e., if 3SAT has a subexponential algorithm—then we’re left with unexplained “spooky action at a distance.” \u00a0How do the algorithms and the reductions manage to coordinate with each other, every single time, to avoid spilling the subexponential secret?<\/p>\n

Notice that, contrary to Lubo\u0161’s loud claims, there’s no “symmetry” between P=NP and P\u2260NP in these arguments. \u00a0Lower bound proofs are much<\/em> harder to come across than either algorithms or reductions, and there’s not really a mystery about why: it’s hard to prove a negative! \u00a0(Especially when you’re up against known mathematical barriers, including relativization, algebrization, and natural proofs.) \u00a0In other words, even under the assumption that lower bound proofs exist<\/em>, we now understand a lot about why the existing mathematical tools can’t deliver them, or can only do so for much easier problems. \u00a0Nor can I think of any example of a “spooky numerical coincidence” between two unrelated-seeming results, which would’ve yielded a proof of P\u2260NP had some parameters worked out differently. \u00a0P=NP and P\u2260NP\u00a0can look like “symmetric” possibilities only if your symmetry is unbroken by knowledge<\/em>.<\/p>\n

Imagine a pond with small yellow frogs on one end, and large green frogs on the other. \u00a0After observing the frogs for decades, herpetologists conjecture that the populations represent two distinct species with different evolutionary histories, and are not interfertile. \u00a0Everyone realizes that to disprove this hypothesis, all it would take would be a single example of a green\/yellow hybrid. \u00a0Since (for some reason) the herpetologists\u00a0really care<\/em> about this question, they undertake a huge program of breeding experiments, putting thousands of yellow female frogs next to green male frogs (and vice versa) during mating season, with candlelight, soft music, etc. \u00a0Nothing.<\/p>\n

As this green vs. yellow frog conundrum grows in fame, other communities start investigating it as well: geneticists, ecologists, amateur nature-lovers, commercial animal breeders, ambitious teenagers on the science-fair circuit, and even some extralusionary<\/a> physicists hoping to show up their dimwitted friends in biology. \u00a0These other communities try out hundreds of exotic breeding strategies that the herpetologists hadn’t considered, and contribute many useful insights. \u00a0They also manage to breed a larger, greener, but still yellow frog—something that, while it’s not a “true” hybrid, does have important practical applications for the frog-leg industry. \u00a0But in the end, no one<\/em> has any success getting green and yellow frogs to mate.<\/p>\n

Then one day, someone exclaims: “aha!<\/em> \u00a0I just found a huge, previously-unexplored part of the pond where green and yellow frogs live together<\/em>! \u00a0And what’s more, in this part, the small yellow frogs are bigger and greener than normal, and the large green frogs are smaller and yellower!”<\/p>\n

This is exciting: the previously-sharp boundary separating green from yellow has been blurred! \u00a0Maybe the chasm can<\/em> be crossed after all!<\/p>\n

Alas, further investigation reveals that, even in the new part of the pond, the two frog populations still stay completely separate. \u00a0The smaller, yellower frogs there will mate with other<\/em> small yellow frogs (even from faraway parts of the pond that they’d never ordinarily visit), but never, ever with the larger, greener frogs even from their own part. \u00a0And vice versa. \u00a0The result? \u00a0A discovery that could have falsified the original hypothesis has instead strengthened<\/em>\u00a0it—and precisely because<\/em> it could’ve\u00a0falsified it but didn’t.<\/p>\n

Now imagine the above story repeated a few dozen more times—with more<\/em> parts of the pond, a neighboring pond, sexually-precocious tadpoles, etc. \u00a0Oh, and I forgot to say this before, but imagine that doing a DNA analysis, to prove <\/em>once and for all that the green and yellow frogs had separate lineages, is extraordinarily difficult. \u00a0But the geneticists know<\/em> why it’s so difficult, and the reasons have more to do with the limits of their sequencing machines and with certain peculiarities of frog DNA, than with anything about these\u00a0<\/em>specific frogs. \u00a0In fact, the geneticists did<\/em> get the sequencing machines to work for the easier cases of turtles and snakes—and in those cases, their results usually dovetailed well with earlier guesses based on behavior. \u00a0So for example, where reddish turtles and bluish turtles had never been observed interbreeding, the reason really\u00a0did<\/em> turn out to be that they came from separate species. \u00a0There were some surprises, of course, but nothing even remotely as shocking as seeing the green and yellow frogs suddenly getting it on.<\/p>\n

Now, even after all this, someone could saunter over to the pond and say: “ha, what a bunch of morons! \u00a0I’ve never even seen<\/em> a frog or heard one croak, but I know that you haven’t proved anything! \u00a0For all you know, the green and yellow frogs will start going at it tomorrow. \u00a0And don’t even tell me about ‘the weight of evidence,’ blah blah blah. \u00a0Biology is a scummy mud-discipline. \u00a0It has no ideas or principles; it’s just a random assortment of unrelated facts. \u00a0If the frogs started mating tomorrow, that would just be another brute, arbitrary fact, no more surprising or unsurprising than if they didn’t<\/em> start mating tomorrow. \u00a0You jokers promote the ideology that green and yellow frogs are separate species, not because the evidence warrants it, but just because it’s a convenient way to cover up your own embarrassing failure to get them to mate. \u00a0I could probably breed them myself in ten minutes, but I have better things to do.”<\/p>\n

At this, a few onlookers might nod appreciatively and say: “y’know, that guy might be an asshole, but let’s give him credit: he’s unafraid to speak truth to competence.”<\/p>\n

Even among the herpetologists, a few might beat their breasts and announce: “Who’s to say he isn’t right? \u00a0I mean, what do we really<\/em>\u00a0know? \u00a0How do we know there even is<\/em> a pond, or that these so-called ‘frogs’ aren’t secretly giraffes? \u00a0I<\/em>, at least, have some small measure of wisdom, in that I know that I know nothing.”<\/p>\n

What I want you to notice is how scientifically worthless<\/em>\u00a0all of these comments are. \u00a0If you wanted to do actual research on the frogs, then regardless<\/em> of which sympathies you started with, you’d have no choice but to ignore the naysayers, and proceed as if<\/em> the yellow and green frogs were different species. \u00a0Sure, you’d have in the back of your mind that they might be the same; you’d be ready to adjust your views if new evidence came in. \u00a0But for now, the theory that there’s just one species, divided into two subgroups that happen<\/em> never to mate despite living in the same habitat, fails miserably at making contact with any of the facts that have been learned. \u00a0It leaves too much unexplained; in fact it explains nothing.<\/p>\n

For all that, you might ask, don’t the naysayers occasionally turn out to be right? \u00a0Of course they do! \u00a0But if they were\u00a0right more<\/em> than occasionally, then science wouldn’t be possible. \u00a0We would still be in caves, beating our breasts and asking how we can know that frogs aren’t secretly giraffes.<\/p>\n

So, that’s what I think about P and NP. \u00a0Do I expect this post to convince everyone? \u00a0No—but to tell you the truth, I don’t want<\/em>\u00a0it to. \u00a0I want it to convince most<\/em> people, but I also want a few<\/em>\u00a0to continue speculating that P=NP.<\/p>\n

Why, despite everything I’ve said, do I want maybe-P=NP-ism not to die out entirely? \u00a0Because alongside the P=NP carpers, I also often hear from a second<\/em> group of carpers. \u00a0This second group says that\u00a0P and NP are so obviously, self-evidently<\/strong> unequal that the quest to separate them with mathematical rigor is quixotic and absurd. \u00a0Theoretical computer scientists should quit wasting their time struggling to understand truths that don’t need<\/em> to be understood, but only accepted, and do something useful for the world. \u00a0(A natural generalization of this view, I guess, is that all<\/em>\u00a0basic science should end.) \u00a0So, what I really<\/em> want is for the two opposing groups of naysayers to keep each other in check, so that those who feel impelled to do so can\u00a0get on with the fascinating quest to understand the ultimate limits of computation.<\/p>\n

\n

Update (March 8):<\/strong><\/span> At least eight readers have by now emailed me, or left comments, asking why I’m wasting so much time and energy arguing with Lubo\u0161 Motl. \u00a0Isn’t it obvious<\/em> that, ever since he stopped doing research around 2006 (if not earlier), this guy has completely lost his marbles? \u00a0That he’ll never, ever<\/em> change his mind about anything?<\/p>\n

Anyway, my goal here was never<\/strong> to convince Lubo\u0161. \u00a0I was writing, not for him, but for my other readers: especially for those genuinely unfamiliar with these interesting issues, or intimidated by Lubo\u0161’s air of certainty. \u00a0I felt like I owed it to\u00a0them<\/em>\u00a0to set out, clearly and forcefully, certain facts that all complexity theorists have encountered in their research, but that we hardly ever bother to articulate. \u00a0If you’ve never studied physics, then yes, it sounds crazy that there would be quadrillions of invisible neutrinos coursing through your body. \u00a0And if you’ve never studied computer science, it sounds crazy that there would be an “invisible electric fence,” again and again just barely<\/em> separating what the state-of-the-art approximation algorithms can handle from what the state-of-the-art PCP tools can prove is NP-complete. \u00a0But there it is, and I wanted everyone else at least to see<\/em> what the experts see, so that their personal judgments about the likelihood of P=NP could be informed by seeing it.<\/p>\n

Lubo\u0161’s response to my post disappointed me (yes, really!). \u00a0I expected it to be nasty and unhinged, and so it was. \u00a0What I didn’t<\/em> expect was that it would be so intellectually lightweight. \u00a0Confronted with the total untenability of his foot-stomping distinction between “continuous math” (where you can have justified beliefs without proof) and “discrete math” (where you can’t), and with\u00a0exactly the sorts of “detailed, confirmed predictions” of the P\u2260NP hypothesis that he’d declared impossible,\u00a0Lubo\u0161’s response was simply to repeat his original misconceptions, but louder.<\/p>\n

And that brings me, I confess, to a second reason for my engagement with Lubo\u0161. \u00a0Several times, I’ve heard people express sentiments like:<\/p>\n

Yes, of course<\/em>\u00a0Lubo\u0161 is a raging jerk and a social retard. \u00a0But if you can just get past that, he’s so sharp and intellectually honest! \u00a0No matter how many people he needlessly offends, he always tells it like it is.<\/p>\n

I want the nerd world to see—in as stark a situation as possible—that the above is not correct. \u00a0Lubo\u0161 is\u00a0wrong much of the time,\u00a0and he’s intellectually dishonest.<\/p>\n

At one point in his post, Lubo\u0161\u00a0actually compares computer scientists who find P\u2260NP a plausible working hypothesis to his even greater nemesis: the “climate cataclysmic crackpots.” \u00a0(Strangely, he forgot to compare us to feminists, Communists, Muslim terrorists, or loop quantum gravity theorists.) \u00a0Even though the P versus NP and global warming issues might not seem<\/em>\u00a0closely linked, part of me is thrilled that Lubo\u0161\u00a0has connected them as he has. \u00a0If, after seeing this ex-physicist’s “thought process” laid bare on the P versus NP problem—how his arrogance and incuriosity lead him to stake out a laughably-absurd position; how his vanity then causes him to double down after his errors are exposed—if, after seeing this, a single person is led to\u00a0question Lubo\u0161ian epistemology more generally, then my efforts will not have been in vain.<\/p>\n

Anyway, now that I’ve finally unmasked Lubo\u0161—certainly to my own satisfaction, and I hope<\/em> to that of most scientifically-literate readers—I’m done with this. \u00a0The physicist John Baez is rumored to have said: “It’s not easy to ignore Lubo\u0161, but it’s ALWAYS worth the effort.” \u00a0It took me eight years, but I finally see the multiple layers of profundity hidden in that snark.<\/p>\n

And thus I make the following announcement:<\/p>\n

For the next three years, I, Scott Aaronson, will not respond to anything Lubo\u0161 says, nor will I allow him to comment on this blog.<\/strong><\/p>\n

In March 2017, I’ll reassess my Lubo\u0161\u00a0policy. \u00a0Whether I relent will depend on a variety of factors—including whether\u00a0Lubo\u0161 has gotten the professional help he needs (from a winged pig, perhaps?) and changed his behavior; but also, how much my own quality of life has improved in the meantime.<\/p>\n

\n

Another Update (3\/11):<\/span><\/b> There’s some further thoughtful discussion of this post over on Reddit<\/a>.<\/p>\n

\n

Another Update (3\/13):<\/span><\/b> Check out my MathOverflow question<\/a> directly inspired by the comments on this post.<\/p>\n

\n

Yet Another Update (3\/17):<\/span><\/b> Dick Lipton and Ken Regan now have a response<\/a> up to this post. My own response is coming soon in their comment section. For now, check out an excellent comment<\/a> by Timothy Gowers, which begins “I firmly believe that P\u2260NP,” then plays devil’s-advocate by exploring the possibility that in this comment thread I called P being ‘severed in two,’<\/a> then finally returns to reasons for believing that P\u2260NP after all.<\/p>\n","protected":false},"excerpt":{"rendered":"

Out there in the wider world—OK, OK, among Lubo\u0161 Motl, and a few others who comment on this blog—there appears to be a widespread opinion that P\u2260NP is just “a fashionable dogma of the so-called experts,” something that’s no more likely to be true than false. \u00a0The doubters can even point to at least one […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5],"tags":[],"class_list":["post-1720","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1720","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1720"}],"version-history":[{"count":31,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1720\/revisions"}],"predecessor-version":[{"id":3008,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1720\/revisions\/3008"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1720"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1720"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1720"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

Yes. \u00a0In fact, I’ve noticed repeatedly that, even when Lubo\u0161\u00a0is wrong about a straightforward factual<\/em> matter, he never really\u00a0admits error: he just switches, without skipping a beat, to some other way to attack his interlocutor. \u00a0(To give a small example: watch how he reacts<\/a> to being told that graph isomorphism is neither known nor believed to be NP-complete. \u00a0Caught making a freshman-level error about the field he’s attacking, he simply rants about how graph isomorphism is just as “representative” and “important” as NP-complete problems anyway, since no discrete math question is ever more or less “important” than any other; they’re all equally contrived and arbitrary. \u00a0At the Lubo\u0161\u00a0casino, you lose even when you win! \u00a0The only thing you can do is stop playing and walk away.)<\/p>\n