HTTPS / Kurtz / eclipse / Charlottesville / Blum / P vs. NP
This post has a grab bag of topics, unified only by the fact that I can no longer put off blogging about them. So if something doesn’t interest you, just scroll down till you find something that does.
Great news, everyone: following a few reader complaints about the matter, the scottaaronson.com domain now supports https—and even automatically redirects to it! I’m so proud that Shtetl-Optimized has finally entered the technological universe of 1994. Thanks so much to heroic reader Martin Dehnel-Wild for setting this up for me.
Update 26/08/2017: 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.
Last weekend, I was in Columbia, South Carolina, for a workshop to honor the 60th birthday of Stuart Kurtz, 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, 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. (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.)
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.
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?
Having seen it, I can now tell you the deal, if you missed it and prefer to read about it here rather than 10500 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 at the sun, at all the weird stuff going on around its disk.
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 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 experience.)
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.
For me, the biggest lesson the eclipse drove home was the logarithmic nature of perceived brightness (see also Scott Alexander’s story). Like, the sun can be more than 90% occluded, and yet it’s barely a shade darker outside. And you can still only look up with glasses so dark that they blot out everything except 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.
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:
Shtetl-Optimized condemns Nazis, as well as anyone who knowingly marches with Nazis or defends them as “fine people.”
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 to have condemned Trump that way also.
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, before it had become the fully thermonuclear issue that it is now. In an overnight operation, UT Austin has taken down its statues of Robert E. Lee, Albert Johnston, John Reagan, and Stephen Hogg. (I confess, the postmaster general of the Confederacy wouldn’t have been my #1 priority for removal. And, genuine question: what did Texas governor Stephen Hogg do that was so awful for his time, besides naming his daughter Ima Hogg?)
A final thing to talk about—yeah, we can’t avoid it—is Norbert Blum’s claimed proof of P≠NP. 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:
To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.
Many people misunderstood me to be saying that I’d again 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.
Speaking of which, some friends and I recently had an awesome idea. Just today, I registered the domain name haspvsnpbeensolved.com. 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.
I have nothing bad to say about Norbert Blum, who made important contributions including the 3n circuit size lower bound for an explicit Boolean function—something that stood until very recently as the world record—and whose P≠NP paper was lucidly written, passing many of the most obvious checks. And I received a bit of criticism for my “dismissive” stance. Apparently, 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≠NP proof will necessarily be so difficult that it will need to “await the Second Coming of Christ.” Luca Trevisan’s reaction to that is worth quoting:
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.
On reflection, though, Mubos has a point: all of us, including me, should keep an open mind. Maybe P≠NP (or P=NP!) is vastly easier to prove than most experts think, and is susceptible to a “fool’s mate.”
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≠NP proof was irreparably flawed, and the consensus has stood since that time.
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 what’s popular or expedient to say.
The background to Blum’s attempt, the counterexample that shows the proof has to fail somewhere, and the specifics of what appears to go wrong have already been covered at length elsewhere: see especially Luca’s post, Dick Lipton’s post, John Baez’s post, and the CS Theory StackExchange thread.
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 circuits, which consist entirely of Boolean AND and OR gates—so that they also work for general (non-monotone) circuits, consisting of AND, OR, and NOT gates. Everyone agrees that, if this succeeded, it would imply P≠NP.
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ïvely hoped: if they did, they’d imply not merely that P doesn’t contain NP, but also that P doesn’t contain itself.
Blum was aware of all this, and gave arguments as to why his approach evades the Matching counterexample. The trouble is, there’s another counterexample, which Blum doesn’t address, called Tardos’s function. This is a weird creature: it’s obtained by starting with a graph invariant called the Lovász theta function, 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, Tardos achieved her goal, which was to produce a monotone function that all 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.
Of course, this merely tells us that Blum’s proof must have 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 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.
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≠NP 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.
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,” they’re every bit as powerful as general circuits. However, insofar as it’s possible to prove superpolynomial lower bounds on monotone circuit size, it’s possible only because monotone circuits are ridiculously less expressive than general Boolean circuits for the problems in question. E.g., it’s possible only because monotone circuits aren’t expressing pseudorandom functions, and therefore aren’t engaging the natural proofs barrier or most of the other terrifying beasts that we’re up against.
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≠NP? 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: no, not a logical impossibility, but something that’s safe to bet against at 10,000:1 odds.
During the discussion of Deolalikar’s earlier P≠NP claim, I once compared betting against a proof that all sorts of people are calling “formidable,” “solid,” etc., to standing in front of a huge pendulum—behind the furthest point that it reached the last time—even as it swings toward your face. Just as certain physics teachers stake their lives on the conservation of energy, so I’m willing to stake my academic reputation, again and again, on the conservation of circuit-lower-bound difficulty. And here I am, alive to tell the tale.
Follow
Comment #1 August 25th, 2017 at 11:51 pm
Mubos Lotl’s thoughts are extremely deep and it would be wise for you to sit down and silently listen to his wisdom.
Not only he is right that your opinions about unproven theorems are full of irrational prejudices. He was also able to switch 200,000 comments on his blog from Echo/Haloscan/JS-Kit to Disqus and now he had to successfully change all the URLs for comments not not disappear when he redirected the blog to HTTPS as well.
Can you code at all?
Otherwise your attempted character assassination motivated by your extreme ideology is something that the people who have lived in Nazi Germany and the Soviet bloc know too well.
Aaronson, people like you are the reason why fine Americans are gradually concluding that all supporters of the Democratic Party are dishonest totalitarian filth.
Sincerely Yours, Bill Clinton
Comment #2 August 26th, 2017 at 1:10 am
Hey Scott (let’s see if comments work now), a while back you mentioned intending to write a post someday about why lower bounds proofs are so bloody hard. I’d still be very interested in reading something like that, or if there’s already an article or paper explaining it, a pointer would be great.
Someone on Stackexchange mentioned they had spoken with Razborov about Blum’s paper, and Razborov said he had read it and immediately spotted the counterexample. It made me think that maybe Razborov, Tardos, and other people working in the area at the time were looking for proofs like the one Blum thought he found, so Tardos’ function is in some sense another barrier result that Razborov immediately knew to check for. Does that sound plausible? Have the issue come up before, in the long history of unsuccessful P vs NP proofs? Thanks.
Comment #3 August 26th, 2017 at 2:12 am
Comments now appear to be working. Sorry for the pause in regular service!
Comment #4 August 26th, 2017 at 3:09 am
In the debates over the best response to hateful groups such as those marching in Charlottesville, the following piece is the best I have seen. It feels as though it should be required reading.
https://theconversation.com/how-should-we-protest-neo-nazis-lessons-from-german-history-82645
(The piece briefly mentions a vastly under-reported incident on inauguration day in which a Milo Yiannopoulos supporter shot a counter-protester, who was intervening in a dispute, on campus – a gun-free zone – outside the venue where Yiannopoulos was due to speak. The shooter claimed self-defense. This was a couple of weeks before his scheduled talk on the UC Berkeley campus was cancelled. Somehow this incident was never picked up by the national media. It did take several months before enough evidence was accumulated for charges to be laid and I am not sure when it is going to trial.)
Comment #5 August 26th, 2017 at 4:23 am
>> the burden of having the right instincts about virtually everything
OMG , so what does your instinct say about: GR=QM and also dark matter (vs modified gravity), the many worlds and the multiverse and last but not least the 4th season of Black Mirror?
Comment #6 August 26th, 2017 at 4:38 am
asdf #2: Yes, that sounds plausible, but for the record, Razborov is not commenting publicly about P vs. NP proofs. The quote from him on StackExchange should not be considered reliable (even though I think the quote is correct, regardless of who said it).
Comment #7 August 26th, 2017 at 4:52 am
wolfgang #5:
GR=QM: I think Lenny’s statements of this kind need to be interpreted poetically, in which case they often contain many deep insights. It’s in no sense literally true that GR and QM are the same thing.
Dark matter vs modified gravity: Dark matter.
4th season of Black Mirror: Sorry, never saw that show or even heard of it, so my instincts, uncanny as they may be, have nothing to work with.
Comment #8 August 26th, 2017 at 6:35 am
“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≠NP? 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 in such a scenario, will the process of trying to find that minor tweak be still mathematics? It somehow sounds more like solving arbitrary NP complete problems to me.
Comment #9 August 26th, 2017 at 7:56 am
Apparently, nobody had a problem with Thomas Hogg’s statue but it was part of an exhibit with other statues they DID have a problem with, so they had to remove it as well:
http://thefacts.com/news/article_64357659-84c2-5783-b189-23dcd6735d34.html
Comment #10 August 26th, 2017 at 8:03 am
Hooray for working comments.
Question: is there a decent chance that Blum’s work will be salvageable to get a weaker result, like say a superlinear bound on 3SAT or maybe an on the linear lower bound constant? Or this the flaw in Theorem 6 so deep as to render this essentially useless?
Comment #11 August 26th, 2017 at 8:21 am
I checked http://haspvsnpbeensolved.com/ and it shows an error message. Does this confirm that P vs. NP is undecidable?
Comment #12 August 26th, 2017 at 8:30 am
I recently had a “naive” idea for proving ALogTime != PH, or at least for better understanding why proving this is hard. The outcome from “investing time” into that idea so far is that I better understand now why even proving uniform TC^0 != PH will be hard: Both ALogTime (=uniform NC^1) and uniform TC^0 are indeed powerful! Addition, multiplication, and division (i.e. especially all operation of modulo arithmetic) are all in DLogTime-uniform TC^0. Recognition of Dyck languages (the languages of balanced parentheses of k different kind) is in TC^0 too, in fact it is TC^0 complete. And ALogTime is even able to simulate Input-Driven Pushdown Automata, i.e. the problem to recognise the languages recognised by (what got rediscovered recently under the name of visibly pushdown automata and of) nested word automata is in ALogTime, in fact it is NC^1 complete.
Based on a recent idea by Joseph Van Name, I had the idea to actually benefit (at least theoretically) from that unexpected situation, namely to motivate hardware manufacturers to develop architectures which really allow to benefit from that power.
Scott, I write this here, because you wrote
I would like to know your opinion on three related questions:
(1) Would you agree with Lance Fortnow that if somebody asks whether such questions are worth studying, the answer is almost always yes? Note that I am just asking about the person doing the studying here (i.e. me in the case above), not about whether it will benefit the scientific field.
(2) Do you have an opinion about attempts like the one from Joseph Van Name and my idea derived from it to convince hardware manufacturers to try to turn conclusions about theoretical advantages from abstract studies into actual hardware architectures?
(3) Does my “naive” idea (or something similar derived from it) has any chance of proving ALogTime != PH (or TC^0 != NP, if you prefer)? It could be something like showing that recognition of Dyck languages is complete for TC^0 under some ridiculously weak notion of reduction like DLogTime-uniform NC^0 reductions (or even rational-uniform NC^0 reductions, as an example of a still weaker notion of reduction), and then show that some specific language from NP cannot be reduced by such a ridiculously weak reduction to recognition of Dyck languages?
Comment #13 August 26th, 2017 at 8:45 am
The real million dollar question is: who is this vloodin? Given that idolvon and vloodin are anagrams, maybe his real name is an anagram of this as well?
Comment #14 August 26th, 2017 at 11:19 am
(1) Ups, that post about “If an ugrad asks `is field X worth studying’ the answer is almost always yes” was actually from Bill Gasarch, not from Lance Fortnow.
(3) A bit more honest and a bit more concrete, the result which I actually hope to achieve by my “naive” idea is ALogTime != P. The crucial capability missing from input-driven pushdown automata is variable binding. One could try to generalise the nesting structure on words to an acyclic graph structure, and show that finite automata on words with an acyclic graph structure recognise a strict superset of languages recognised by finite automata on words with a nesting structure. The step were I guess that my idea/plan will actually fail is finding a suitably weak notion of reduction, which is weak enough to carry over the separation between nesting (tree) and acyclic structure, and strong enough that one can prove completeness of input-driven pushdown automata for ALogTime.
Comment #15 August 26th, 2017 at 11:20 am
Trump just pardoned a thuggish police officer. Perhaps he is testing the waters before he pardons his co-traitors. I think Scot t was absolutely right that Trump is a wannabe-dictator.
Comment #16 August 26th, 2017 at 11:39 am
Hi Scott – I volunteer to make the website 🙂
Comment #17 August 26th, 2017 at 11:50 am
1) Has Norbert Blum retracted or made some comment on the Tardos counterexample?
2) I used to think about P NE NP attempts: I doubt they showed P NE NP but maybe they showed something interesting. So far this has not happened. Since N Blum’s attempt is a serious attempt by a serious person, perhaps this time something interesting will come out of it.
3) There seemed to be less excitement about this attempt then about Deolalikar’s attempt. Is this because the issue was found earlier? because of Deo’s attempt later attempts are dealt with more skepticism? Any ideas?
Comment #18 August 26th, 2017 at 12:43 pm
“Bill Clinton” #1: I can see that your IP address is from the Czech Republic. Whether you’re “Mubos” himself or just a close ally, please get back on your meds.
Comment #19 August 26th, 2017 at 12:52 pm
Michael #9:
Apparently, nobody had a problem with [Stephen] Hogg’s statue but it was part of an exhibit with other statues they DID have a problem with, so they had to remove it as well
Thanks! Yeah, that was my guess—that Hogg’s crime was simply to consort with Confederates while in statue form. (President Fenves, in his email, mentioned the possibility of reinstalling the Hogg statue somewhere else.)
Comment #20 August 26th, 2017 at 1:01 pm
Joshua #10:
is there a decent chance that Blum’s work will be salvageable to get a weaker result, like say a superlinear bound on 3SAT or maybe an on the linear lower bound constant? Or this the flaw in Theorem 6 so deep as to render this essentially useless?
Note that a superlinear lower bound for 3SAT would already be one of the most striking circuit lower bounds ever (!).
I don’t know the answers to your questions, but much like with Deolalikar, I’d say that the ball is now firmly in Blum’s court, or the court of anyone else who thinks something might be salvageable from his effort, to sift through and see. It’s not something I’d invest my own time on.
Comment #21 August 26th, 2017 at 1:07 pm
I think people on the internet took the latest NP \notin P/poly claim seriously because they don’t realize how far we are from that goal. Even NEXP \notin NC^1 would be a breakthrough. There are intermediate problems that ought to be solved first. Why is the claimed breakthrough always P vs. NP, not P vs. PSPACE or TC^0 vs. EXP?
Proving NP \notin P/poly today would be like the Wright brothers rolling out a Boeing 747 in 1905. Sure, it’s not physically impossible, but realistically 64 more years of experience were needed.
Comment #22 August 26th, 2017 at 1:18 pm
gentzen #12 and #14: I don’t know enough to give you detailed feedback about your specific approach, or the approach of Joseph Van Name (which I hadn’t even heard of).
In general, yes, I think complexity theory is worth studying—not surprisingly, or I wouldn’t study it myself!
But don’t we actually know that ALogtime is equal to P? That’s what the Zoo says…
For a student, or someone else just getting into the field, my strong suggestion is to get your feet wet by solving some “ordinary,” non-hyper-mega-famous problems, rather than just walking straight up to the P vs. NP or even TC0 vs. PH questions and asking them to marry you. Browse some recent STOC/FOCS/ITCS/CCC papers for lots of examples of problems at or near the current frontier.
Comment #23 August 26th, 2017 at 1:27 pm
Adam Chalmers #16: Thanks so much!! We’ll be in touch. And please stay safe in Texas during the hurricane.
(Note: I’m in Dresden, Germany right now, where I’m giving a TEDx talk tomorrow on “What Quantum Computing Isn’t.” Being as it’s August 2017 rather than February 1945, it’s safer to be here than in Austin…)
Comment #24 August 26th, 2017 at 1:35 pm
GASARCH #17: No, I haven’t seen anything further from Blum—no retraction, clarification, nothing.
Yes, I do think it’s plausible that the Deolalikar experience made the public response more muted this time around, although I can’t be sure.
Readers: If you followed both the Deolalikar and Norbert Blum attempts, and if the former already made you hyperventilate less about the latter, then imagine just how little you’d hyperventilate after having seen hundreds of these things! Then you’ll begin to understand what it’s like for people in the field.
Comment #25 August 26th, 2017 at 1:36 pm
tas #21: Yes, that’s precisely right.
Comment #26 August 26th, 2017 at 4:17 pm
Scott #22: The zoo says
Your link was to “AL: Alternating L”. So now I learned that [CKS81] showed AL=P, which I find interesting.
I know Joseph Van Name from his interest in lattice theory, but his idea here was about reversible computing. Reversible computing is as powerful as irreversible computing (at least in theory), and reversible computing should require less energy (at least in theory). Joseph’s idea was that, hence it would be a good idea to influence hardware manufacturers to develop computers exploiting the benefits or reversible computing. And since I learned now that TC^0 and NC^1 are quite powerful, I employed the same logic that one should influence hardware manufacturers to develop hardware architectures exploiting the (theoretical) benefits of TC^0 and NC^1.
Regarding your answer to (1) whether you agree with Bill Gasarch, your answer basically assumes “… they really want to do RESEARCH, …” and hence your answer agrees with Bill in the sense that they should avoid “too hard” problems in that case. But if the goal is just “or at least for better understanding why proving this is hard,” would you still recommend to avoid “the P vs. NP or even TC0 vs. PH questions”?
(Your answer to (3) and even letting those two comments through moderation at all shows that you really keep an open mind. Sorry for testing, I just couldn’t resist.)
Comment #27 August 26th, 2017 at 4:42 pm
Prof. Blum hS a seminar scheduled for Monday. Link from cst.se thread
http://domino.mpi-inf.mpg.de/internet/events.nsf/…
Comment #28 August 26th, 2017 at 4:52 pm
Peter #13: Old Vino!
Comment #29 August 26th, 2017 at 5:02 pm
Hey Scott,
Happy to help you with your ‘haspvsnpbeensolved.com’ web page idea. I think it’s great. Reach out and let me know.
Comment #30 August 26th, 2017 at 5:47 pm
Aaron #29: Thanks so much for the offer! Adam Chalmers is already on, but we’ll be sure to get in touch if we can use your help.
Comment #31 August 26th, 2017 at 8:19 pm
https://domino.mpi-inf.mpg.de/internet/events.nsf/3802238747b751e6c12564c10080ba87/c49c4625bee6addfc1258180003ef6a4!OpenDocument
ungarbled url from #27, sorry about bad paste earlier.
Comment #32 August 26th, 2017 at 9:27 pm
instead of just gleefully mocking incorrect proof attempts and public understanding of CS in general, it would be very cool if serious scientists were willing to donate some time to checking proofs and offering a few lines of refutation. a volunteer effort. know its considered laughable by many, but to me it seems like a quite reasonable public relations/ educational project, esp if the refutations were published online. it could do some real good, maybe decrease the bogus proof attempts. there are a few scattered papers like this on arxiv. even better, how about some discussion about proof attacks? this happens all the time on polymath for other problems, why not CS? are the mathematicians more together than the computer scientists? lol… the cstheory.se post now has 77Khits and proves theres a huge popsci audience/ thirst for this topic.
Comment #33 August 26th, 2017 at 9:33 pm
[…] Many Topics by Scott Aaronson – Misc Topics: HTTPS / Kurtz / eclipse / Charlottesville / Blum / P vs. NP […]
Comment #34 August 26th, 2017 at 11:20 pm
vzn #32: But people did do that. And given the amount of time it takes, I’m incredibly grateful to them—if we all had to do it for every mistaken claim, then we’d never do anything else.
Comment #35 August 26th, 2017 at 11:32 pm
Scott,
I find your proposed website haspvsnpbeensolved.com very off putting.
Every generation has its academic gatekeepers -you belong to this group clearly- and the people who do groundbreaking work that set entire disciplines in a totally different directions. Sometimes these two kinds of people are the same, but in many cases, they are not. Gatekeepers are absolutely necessary to help in the task of separating good work from junk. Now there is a fine line between serious attempts to perform the gatekeeper job and ridiculing those how work on the hard stuff out of love for the discipline but outside the institutions gatekeepers have set up.
It seems to me that your website idea belongs to the “ridiculing” column. Do you seriously believe that people, with their own names, will submit papers to one such website to pass your sanity test? Most likely the effect will be the opposite: when in doubt, people will rather keep their ideas private rather than risking being shamed worldwide by your website.
There are many examples of people with little to no formal education that went on to make outstanding contributions during their lifetimes. Take for example Michael Faraday. A person like him wouldn’t stand a chance in the kind of “shaming dystopia” you propose.
You should be encouraging people, regardless of their background, to work on these tough problems, not threaten them with “worldwide shame” if they dare publish something that later turns out to be a erroneous. There are errors that turned out to be fundamental to make progress in hard problems. Take for example the Taniyama–Shimura conjecture (now known as the modularity theorem thanks to Andew Wiles). One of its proponents, https://en.wikipedia.org/wiki/Yutaka_Taniyama , was mistake prone and in fact the first version of the conjecture he proposed was incorrect but was later fixed through his work with Shimura. Taniyama ended up committing suicide. The wikipedia page says “Taniyama’s ideas had been criticized as unsubstantiated and his behavior had occasionally been deemed peculiar.”
So please, let’s be a bit more positive about these things. It’s awesome that you are a full professor in your late 30s, but that kind of academic career is not a necessary condition to be a successful researcher in mathematics. Sometimes can be in fact, an obstacle.
Comment #36 August 27th, 2017 at 12:49 am
#35: You’re extremely wide of the mark, because I’ve taken pains not to ridicule people for their mistaken P≠NP proofs. I reserve the (good-natured) ridicule for those who excitedly spread wrong P≠NP proofs on social media, oblivious to the whole history of the subject—and especially for those like “Mubos,” who use such proofs as occasions to denigrate a field I love.
Given how much flak I’ve taken online for saying what I think, day after day, with no pseudonym or anything else to protect me—often under pressure from my readers to do so—who could possibly blame me for having a little fun when I turn out, once again, to have been right? 🙂
One of the central satisfactions of my career so far has been to mentor students who hardly anyone else believed in at the time—some of whom have since gone on to become superstars. Those students were working, not on reaching the moon with pogo-sticks (say, by trying to prove P≠NP), but on real advances that get 1% as much attention—sometimes problems that no one else at the time understood or cared about, but that the students were led to by their own inner compasses. I don’t need to be lectured about these matters.
Comment #37 August 27th, 2017 at 1:23 am
Scott #35,
Your answer is a red herring. Good for those students you mentored, I suppose, but that is not what I am talking about.
Yes, there are failed proofs of the P vs NP problem produced by people who worked in secrecy, but there are also germs produced by this kind of people. The most recent example that comes to mind is Yitang Zhang and his proof that there are infinitely many pairs of prime numbers that differ by 70 million or less. He was 58 when he published this paper and, according to press accounts http://www.newyorker.com/magazine/2015/02/02/pursuit-beauty , he had worked in a long list of odd jobs before landing, at the age of 46, a lecturer job at the University of New Hampshire.
I guess that what I am trying to say is this: I get you like your academic job and want to help students get academic jobs following the traditional tenure track path: work on tractable problems, get published, get yourself known, attend conferences, develop relationships, etc. But what this post projects is a certain disdain for those who love computer science and mathematics as much as you do and who, for one reason or another, don’t want, or can’t, follow this path and opt for a different one. That’s how I see the whole idea of haspvsnpbeensolved.com, and apparently I am not alone (see vzn #32 comment above). Why the hostility towards these people, that’s the part I don’t understand.
You should do your stuff and restrain from mocking those who work differently. You never know where the next Yitang Zhang might show up and what his/her contribution might be!
Comment #38 August 27th, 2017 at 1:48 am
(Off-topic: thanks Scott for your post on the Google memo. I was away during the commenting period, but thanks all the same to you and Ms. Constantin and Jeffery.)
Ranting off Charlottesville:
Charlottesville saw a rally of swastika and tiki-torch(?) wielding dudes of the white supremacist/Nazi persuasion. No doubt about that, and it’s worth remembering that Nazis were/are a horrible ideology. Trump should have condemned that rally for what it was.
But once that is acknowledged, let’s also give some time to the conservative complaint that rad-left tactics are quite dangerous too. I heard rumors, credible these days, that the Boston “protest” (that the anti-Nazi counter-protest was there to squelch) was basically a black guy being a not-particularly ornery Republican. He’s a Nazi too now?
There are real Nazis out there. But if everyone who isn’t “you” (not you-Scott, you know what I mean) is a Nazi, then that word is meaningless, which is a dangerous place to be. The idea that label stands for is important, if only to avoid that idea.
On P vs NP: I’m an uninformed spectator here so no comment. Maybe when the blog will feature something on parity games (where I’m a decently informed spectator) I might.
Speaking of parity games, big things happened this year and if anyone happens to be in London this September, Highlights of Logic, Games and Automata may be a cool place to go. I wish I could attend, but time pressures elsewhere.
Cheers.
Comment #39 August 27th, 2017 at 2:53 am
#37: Your criticism might make more sense if I’d ever once cast aspersions on Yitang Zhang’s groundbreaking work, or on that of any other “unknown” who made a brilliant mathematical advance. (Zhang, incidentally, is a well-trained mathematician who, alas, had trouble finding a job after moving from China to the US, which is a very different issue from the one you’re talking about.)
On the contrary, I’ve never had anything but praise for society’s “Galoises” and “Ramanujans,” who incidentally were among my main childhood heroes. In some sense, we all start out as unknowns facing an indifferent establishment.
Your criticism might also make more sense if Norbert Blum weren’t himself a well-respected academic, and in fact a CS department chair in Bonn.
I think you underestimate just how easy it is to distinguish a Yitang-Zhang-like bolt-from-the-blue from another failed P≠NP attempt—with that ease demonstrated by the fact that, again and again, the professionals do distinguish them. The differences have nothing to do with the identities of the authors, but are internal and mathematical—part of it’s about comparing the scope of the problem against the new ideas introduced and asking whether they’re even within three orders of magnitude of each other.
(This doesn’t mean there are no ‘edge cases’ that are extremely hard to judge; Mochizuki’s claimed solution to the ABC conjecture is a possible example. But along with these edge cases are a huge number of easier cases.)
Anyway, if P vs. NP does someday get solved, and I don’t take haspvsnpbeensolved.com off the web within like half a day of seeing the solution—that’s the point where I’ll admit you were right. 😉
Comment #40 August 27th, 2017 at 3:26 am
For those interested in the recent history of claims related to P vs NP, Gerhard Woeginger has a P vs NP page where links to claimed proofs are collected. Unlike Scott’s proposed site, the references make no judgements about the validity of the papers and does not expose problems with them. Anyone wishing to check the claims can go there to find the papers.
https://www.win.tue.nl/~gwoegi/P-versus-NP.htm
The link to Norbert Blum’s claimed proof is not yet posted.
Comment #41 August 27th, 2017 at 5:39 am
Scott,
>> the ongoing darkening of the United States
I think you and your country were actually very lucky.
So the US is going through its irrational phase, but instead of a real strongman, like other unlucky countries, you got this bizarre clownshow in the White House.
Putin runs the Kremlin with the efficiency of an ex-KGB officer.
Adolf did not get a majority in parliament, but outmaneuvered his opponents and took over Germany within a few months.
In contrast the TrumpShow was so far unable to even repeal a healthcare law or secure enough funding to begin building his wall. And his nationalist socialist strategist, Steve Bannon, was outsmarted by Ivanka …
In my opinion, the only real danger would the generals around The Donald, but so far they seem to be a moderating, rational influence. As I said, you are really lucky.
Comment #42 August 27th, 2017 at 8:00 am
#39:
Scott, another example of an ‘edge case’ is Royen’s recent proof of the Gaussian correlation inequality. As described in this Quanta article, his proof was almost lost because it didn’t use any new techniques and Royen wasn’t well known in academia.
So, these cases do pop up once in a while, and dismissing attempts outright seems…well too dismissive. Though, of course, you’re going to be right with probability approaching 1.
Comment #43 August 27th, 2017 at 8:23 am
Aside from the proof’s approach looking “too wimpy”, I was immediately suspicious of the paper’s title. Does anyone really think that the paper that solves PvNP is going to be titled “A Solution of the P versus NP Problem”? To me, a paper with that kind of title might as well be called “Hey Look At Me, I Solved PvNP, Give Me Money And Glory”.
This isn’t just an issue of propriety or false modesty. A negative solution to PvNP is certainly going to require some deep new ideas, and if the title doesn’t give any indication as to what those ideas are, there might not be any. (A positive solution might not require deep new ideas, since such a proof could be “just” the construction of a clever new algorithm, but that seems unlikely.)
Comment #44 August 27th, 2017 at 8:23 am
https://www.theguardian.com/science/2017/aug/27/collection-letters-codebreaker-alan-turing-found-filing-cabinet
Collection of letters by codebreaker Alan Turing found in filing cabinet
The correspondence, dating from 1949 to 1954, was found by an academic in a storeroom at the University of Manchester
Comment #45 August 27th, 2017 at 8:29 am
By the way, haspvsnpbeensolved.com is currently redirecting me to the website for the Fairbanks Daily News-Miner (“The Voice of Interior Alaska”). Is that the secret algorithm?
* If even local newspapers in goddamn Alaska say PvNP has been solved, it probably has been.
Comment #46 August 27th, 2017 at 9:30 am
Arnab #42: Let’s take that example and run with it. For the Gaussian correlation inequality to be proved, using “just” a couple pages of manipulations that somehow eluded everyone else, is about the outer limit of such events that we actually observe in reality (which is exactly why it deservedly received so much attention).
And yet there are still many orders of magnitude in plausibility-space between that and P vs NP succumbing to a similar gambit.
So I feel comfortable that, if I’d be willing to register haspvsnpbeensolved.com, but not hasthegaussiancorrelationinequalitybeenproved.com, I’ve picked a line that has plenty of margin on either side of it.
Comment #47 August 27th, 2017 at 10:07 am
Arnab #42
That indeed is another good example. I didn’t know about it, so thanks for mentioning it!
Scott #39
I heard about Mochizuki’s work too. But you still seem to be missing what I am talking about here. A few times you have mentioned this notion about you being right, me being right. It must be a millennial slip. That’s irrelevant to my main point. My main point is not about you being right or me being right, it is about why this notion of dismissing outright somebody’s work because he/she didn’t follow a traditional path to work on a particular problem or didn’t publish it it the right way. According to https://en.wikipedia.org/wiki/Gaussian_correlation_inequality in Royen’s case, another reason it took time for his proof to be accepted is “The proof was not generally known when it was published in 2014, due to Royen’s relative anonymity and his choice to publish the proof in a predatory journal”. Why would have Royen had to publish it somewhere else?
My point is that the communications revolution that started in the 1990s with the availability of the internet to the general public has expanded, not limited, the way people can work in computer science and math problems, including the hard ones. Up until then, if you wanted to work on these problems, being employed at a prestigious institution and being published at prestigious journals were kind of “musts” mostly because that was about the only way there was to be exposed to the most cutting edge and interesting work. We don’t live in that world anymore. I see your haspvsnpbeensolved.com idea more as an attempt to protect a particular way of working on these problems (the traditional one that you have followed) than an attempt to shed light on the validity of attempted proofs.
Let me tell you something. Across knowledge communities there is a revolution going on in the ways people produce revolutionary work. Up until the 1980s or 1990s, people who wanted to work on cutting edge ideas outside academia had only two options: getting a job at a government lab or getting a job at an industrial research laboratory such as IBM’s. That way of working is now gone forever. Many professional bodies such as the IEEE and the ACM have been facing for years the problem of either decreasing or slow growth membership numbers. This is no accident. We live in a flat world and there are many consequences to this, including that the value of belonging to exclusive clubs of knowledge is not as high as it used to be. I just don’t see any upside to haspvsnpbeensolved.com from the point of view of encouraging people to work on the P vs NP problem, but I so see many downsides.
Comment #48 August 27th, 2017 at 10:34 am
Scott #36,
You said, “not on reaching the moon with pogo-sticks (say, by trying to prove P≠NP), but on real advances that get 1% as much attention”.
Is there a proof that one cannot use elementary methods (pogo sticks) to prove that P≠NP? I am not aware of any. Certainly there are proofs that certain techniques cannot prove that P≠NP, but I don’t think you can generalize this to all elementary methods.
Furthermore, the belief that elementary methods cannot prove that P≠NP because problems that are easy to state and difficult to solve cannot have simple solutions is essentially a belief that P=NP, since this is what P=NP means.
Comment #49 August 27th, 2017 at 10:35 am
Wolfgang #41:
Totally agree with you. At a moment when the the racist, dummy, and crazy communities are energized, and a natural leader has come forward and got elected by a fluke, it is indeed fortunate that this leader is an egotistical buffoon, incapable so far of inflicting too much damage.
Comment #50 August 27th, 2017 at 10:43 am
The problem with gatekeepers #47:
I don’t think research that does not follow the usual path is dismissed out of hand. Rather, the situation is that vastly more stuff appears than can be read by anyone. Thus anyone trying to keep up must pick some small portion of new stuff to read, and it is natural to favor the sources that resemble those that have proven fruitful in the past.
Comment #51 August 27th, 2017 at 11:01 am
#47: So, let me get this straight. The mavericks who will prove P≠NP will cheerfully ignore all existing publication and other barriers (as of course they should), and yet they’re going to be scared away because someone made a joke website called haspvsnobeensolved.com?
I certainly agree about the obsolescence of the current journal system, and have been vocal about it for more than a decade—see the archives of this blog! On the other hand, if you want your breakthrough paper to be studied by experts, then one way or another it does need to get someplace where the (ridiculously harried and busy) experts will notice it; that remains the case in our Web 2.0 world.
Comment #52 August 27th, 2017 at 11:06 am
Craig #48: Obviously there’s no proof that you can’t use elementary methods. Indeed, there’s a clear sense in which anything that’s provable at all, is provable with “elementary methods” (say, first-order reasoning about integers and sets).
Now, there’s also no proof that you can’t reach the moon with pogo sticks. And I would guess that in principle, you can.
The point is simply that, if you knew enough to reach the moon with pogo sticks, then you’d almost certainly know enough to have reached it with a rocket long before then!
Comment #53 August 27th, 2017 at 11:47 am
Scott, is there a recording of the talk you gave for Kurtz’s birthday? or alternatively, if you think it’s worth, can you write a transcript of it?
I really enjoyed the one you gave for Avi’s birthday.
Comment #54 August 27th, 2017 at 1:15 pm
#46: Fair enough 🙂
Comment #55 August 27th, 2017 at 1:33 pm
Scott re #7: oh! We’re testing your instincts now? Can I have a go too? Vacuum trains for transcontinental bulk freight transport versus nuclear fusion power plants, which one will we have first in a stage where they are commercially viable enough to reduce greenhouse gas emissions significantly?
Re #36: and not only your students. You’ve popularized the 2.373 result, and mentioned the sparse fast Fourier transform in a comment. I probably wouldn’t have heard about either of these recent developments until perhaps the ultimate edition of TAOCP vol 2.
Comment #56 August 27th, 2017 at 2:11 pm
Scott #51
There are two ideas in your comment that I address separately:
– On haspvsnobeensolved.com, I guess you have a point that those with the attitude and self-confidence to go their own way about P vs NP probably won’t care about the existence of the website. What about impressionable youth? The message these youth need to get is more along the lines of what Andrew Wiles expresses here https://youtu.be/KaVytLupxmo?t=120 . It is OK to be “stuck” in the pursuit of hard problems. If you have a great traditional career, awesome, good for you. But people shouldn’t give up on mathematics or computer science altogether because they didn’t achieve milestone X by age Y. I for one think that the 40 year limit of both the Fields Medal and the Nevanlinna prizes are very pernicious. Maybe they made sense at a time when people led simpler lives and sorted themselves out by their early 20s around what they wanted to do in life (like when the Fields Medals was originally proposed). In 2017, they make absolutely no sense. They -the prizes- over-fit for a particular type of demographic: those who were brought up in a learned environment.
– On your second point about the obsolescence of the current journal system, there is no disagreement there. In fact I see this part of a larger trend of moving from closed learned communities to open learned communities. The world of software is going through a similar process with the most interesting work these days happening in the open source world.
Comment #57 August 27th, 2017 at 2:16 pm
I second Bill Gasarch: the “ball” is now in authors (of this discussed P!=NP proof) hands. Either he explains, why (at which particular place in the construction) his proof fails for the Tardos function, or we can forgive all this “noise” … Proofs “by construction” (not by an argument) are mostly wrong, and are damned difficult to point to “here is the bug”. [I would of course be happy if somebody younger could “catch the cat”.]
On the positive side, I think that his argument still works for (non-monotone) DeMorgan circuits, but for very restricted ones, those where no variable x_i can meet its negation 1-x_i (no annihilations). This restriction is, however, miles away from the P vs. NP question.
Comment #58 August 27th, 2017 at 2:23 pm
Pete #13
Do you think he/she is going to risk giving out his/her identity in a world of planetary “internet shaming”. So far he/she has made very good points on both this and the discussion that surrounded Vinay Deolalikar’s attempt. What about if he/she gets one of his points wrong? Do you think he/she could survive the backlash? For all we know this could be somebody fitting Royen’s profile. In the business world there isn’t anything akin to “tenure” and companies care deeply about reputation. Getting “internet shamed” worldwide is a sure ticket to unemployment in this world.
Comment #59 August 27th, 2017 at 3:06 pm
@The problem with gatekeepers: All the examples you’ve raised were eventually recognized as being correct solutions to the various problems. Sure, some weren’t immediately accepted and spread virally across the internet. But is that so bad? Is there something wrong with taking some time to verify things?
If someone does indeed solve P vs. NP, then I think it will be accepted soon enough.
I think the point of haspvsnpbeensolved.com is to make it clear that there is a simple algorithm for checking P vs. NP papers that is 99.999% accurate. Sure, it’s not 100% accurate, but it’s important to have realistic expectations. Hopefully, hopefully it will help people on the internet develop some more skepticism, like jaded experts have.
Comment #60 August 27th, 2017 at 3:54 pm
jonas #55: Sorry, it’s not that I have instincts about every conceivable question; it’s just that the instincts are preternaturally reliable when I do have them. 🙂
My crystal ball tends to be clearest when judging personal character, or claims about discoveries or inventions already made, or anything resolvable by simple explanatory theories that already exist but that most people dislike for emotional reasons. It’s hazy when trying to make actionable predictions about (e.g.) the timelines for particular future technologies or political upheavals. (As one consequence, it would be nontrivial to use this crystal ball to get rich on the stock market.)
Comment #61 August 27th, 2017 at 3:57 pm
Nick #43:
I damn well hope it’s called that. (Better would be if the title said something about the method, too.) We have enough obscure titles and abstracts that don’t make it clear what the point of an article is and enough papers that bury the lede way down in an appendix somewhere. Please, yes, let’s all be explicit about the consequences of what we’ve proved, specifically the consequences that other people will care about, and not bury them or leave them for the reader to infer. (I will remind people about Terry Tao’s advice for writing papers.)
(People should use more explicit constants too[0]. People act like this is so hard to keep track of when a lot of the time it’s really not.)
(On that note, I mentioned this in an earlier thread, but apparently Harald Helfgott showed that Babai’s quasipolynomial time algorithm for graph isomorphism is in fact runs in time 2^O((log n)^3), faster than Babai’s speculated 2^O((log n)^8)…)
[0]Note: I’m not talking about things like “when we say this algorithm is O(n^2), what’s the constant there”, because there’s a pretty good reason we don’t care about that. But that’s pretty specific to complexity theory and even then doesn’t apply to plenty of the constants there (if something is polynomial time we ought to know the exponent!).
Comment #62 August 27th, 2017 at 4:00 pm
TPWG #58:
You have this totally backwards. There have been two supposed proofs that many of the world’s experts were examining for flaws. Being the one to find the error is rather a big deal. The same person found the error in both cases, which is totally remarkable. The fact that she or he chooses to remain anonymous rather than bask in some fame is also remarkable.
Comment #63 August 27th, 2017 at 4:01 pm
#56: It’s like with the wise karate master in a movie, who knows that his first task is to discourage the overeager young student from becoming a karate master himself, and then to see whether the student returns anyway.
Smart but impressionable young people should be guided to any of the thousands of beautiful, enticing open problems on the current research frontier—or better yet, to invent their own problems and models.
I think that, at the current stage of our field’s development, the only people who you want directly working on P vs. NP (if any) are the ones who are such tenacious mofos that they’ll just keep working on it regardless of what anyone says or does to discourage them.
Comment #64 August 27th, 2017 at 4:04 pm
There are NP-complete monotone (slice) functions for which an exponential lower bound on the (monotone) circuit size implies P!=NP. And Razborov has demonstrated exponential (monotone) circuit lower bounds for some NP-Complete monotone functions, such as CLIQUE.
Is there a clear barrier preventing applying Razborov’s technique to slice functions in a similar way?
Comment #65 August 27th, 2017 at 4:08 pm
#58: In the back of my head, I try to keep a running list of all the types of expression that, in the modern world, can get a person fired from their job. If that list now includes … making some minor mistake in generally incisive technical commentary about attempts to prove circuit lower bounds … then it might be time to declare that Shtetl-Optimized had a good 12-year run and throw in the towel. 🙂
Comment #66 August 27th, 2017 at 4:13 pm
Diego #53: Alas, there’s no recording and no slides. I do have handwritten notes, and I could type them up, but this talk was a bit more technical than the Avi permanent talk (it involves, e.g., showing that if SampBPP=SampBQP and NP⊆BPP, then SampBPPA=SampBQPA for all oracles A∈P/poly). Is anyone else interested?
Comment #67 August 27th, 2017 at 4:40 pm
#65 Oh well, you’d be surprised. From personal experience I know both the world of academia (not only from my training years but also from personal connections) and the world of business (from my current occupation). To say that these two are worlds apart would be an understatement.
Let’s begin with revenue sources. In academia, particularly well established institutions like the ones you attended as student or the ones you have been employed, they come fundamentally from three different sources: student tuition, gifts/endowment returns and research contracts. There might be years when individual components of these equations go up or down, but over the long run they all go up and there is no risk that they will ever go down. In businesses, the revenue comes from your customers willing to pay you for what you produce. If you have a monopoly like Google or Facebook, the situation might look indistinguishable from academia except for the fact that while I can name you several companies that went from global dominance to oblivion, I cannot find any academic institution that worldwide reputation that then went bust in the last 100 years. So still, revenues in academia are much more of a sure thing than in the most successful companies of the world.
Then there is “tenure”. Simply put, in business, nobody has anything remotely close to “tenure”. Even founders can be kicked out of the companies they started, as happened to the Cisco founders, Brendan Eich at Mozilla and recently Travis Kalanick at Uber.
This creates very different dynamics at both environments. As a tenured professor, the worst that saying things that might damage the image of the institution you work for can bring you is a lifelong of teaching the crowded introductory courses nobody wants to teach. In business, you can be fired if the powers that be perceive that your actions create a reputational harm to your employer. Note that you don’t need to actually cause decrease on revenues or that your name is brought up by your customers as a reason why they don’t buy your product anymore.
If I had to make any bets, I would say that idolvon/vloodin is probably employed in the private sector or, if he/she works in academia, he/she holds a non tenured position.
Comment #68 August 27th, 2017 at 5:07 pm
TPWG #67: “If I had to make any bets, I would say that idolvon/vloodin is probably employed in the private sector or, if he/she works in academia, he/she holds a non tenured position.”
I regret to inform you that again you have it totally backward. In reality, if idolvon/vloodin is an untenured university person, these contributions would be a moderate step toward becoming tenured. There is ZERO reason anyone would hide this except for fun and mystery.
Comment #69 August 27th, 2017 at 5:41 pm
Raoul Ohio #68
It seems to me you know little about the world of top notch academia. I am talking about the institutions that appear in the top 20 of the Shanghai ranking. There are lots of politics in the process of becoming tenured there. This is not to say that people employed as tenure track faculty at those institutions are unqualified. On the contrary, they are very qualified -being superbly qualified as a necessary condition to being invited to the party-, but because there are many more qualified candidates than slots available, tenure committees know that if they reject tenure for one of the tenure-track professors, at least 10 equally qualified applicants will pop up the moment the position is announced.
In a world like this, the only accepted public comments are those perceived as “non controversial”. The moment they are perceived as controversial, the potential for them being used against the candidate increases. An attempted P vs NP proof is controversial until a consensus emerges on whether it is a valid proof or an invalid proof. So any comments made in the running up to the consensus emerging is, by definition, controversial. That is the great catch 22 of these events and why I am personally against shaming -or creating the perception of shaming- anybody who attempts to work on these problems.
Comment #70 August 27th, 2017 at 6:15 pm
“The problem with gatekeepers”:
I am an outsider, I study and learn from the work of outsiders, I have seen things go badly for outsiders. So why do I find your comments extremely annoying?
First, they are really wide of the mark. You say:
“Do you seriously believe that people, with their own names, will submit papers to one such website to pass your sanity test?”
as if the website were to be a substitute for peer review or other serious forms of assessment. Note, it’s called haspvsnpbeensolved.com, not haveisolvedpvsnp.com. It would not be there for wannabe Turings to receive personal validation, it would be there so members of the public can hear (I guess) a few home truths from an expert in a field where there have already been over 100 wrong papers claiming to decide this issue.
You also refer to
“mocking those who work differently”
and
“this notion of dismissing outright somebody’s work because he/she didn’t follow a traditional path to work on a particular problem or didn’t publish it it the right way”.
Once again, this has no relationship to the purpose of the website, or to what anyone has said so far. The website will equally “evaluate” P-vs-NP claims by well-situated individuals like Deolalikar and Blum, as well as the hopeful unknowns who post on vixra.
And if we are going to talk about outsiders, we don’t get to focus just on the talented ones who got something right, or the unlucky ones who were right but ostracized. What about the incompetents who will never get it right? What about the fact that experts really do know things that amateurs don’t? What about inferior work – from inside *or* outside the academy – that gets hyped?
Comment #71 August 27th, 2017 at 6:40 pm
Scott #39
> Anyway, if P vs. NP does someday get solved, and I don’t take haspvsnpbeensolved.com off the web
Why not just update it if and when that happens? No need to take it off the web.
Comment #72 August 27th, 2017 at 6:52 pm
#69: I’m having trouble recognizing the world you describe in any of my 20 years in academia.
For one thing, you fail to distinguish between publicizing a badly-wrong P≠NP proof (which might indeed hurt someone’s tenure case), and commenting about such a proof on the Internet (which won’t affect anything one way or the other, unless there’s something really extraordinary about the comments). By analogy, no one really cares in tenure cases about how much conventional journal/conference reviewing you did, maybe unless you completely shirked all responsibilities. Assuming there’s no obvious dealbreaker (like an ethics violation), they care about whether your own recent research has made a big enough splash, and whether it’s respected as sufficiently “deep.” Everything else is lower-order trimmings.
For a second thing, do you have any idea how many “controversial” positions I’d already defended on this blog, before MIT decided to tenure me? Doesn’t that count pretty massively against your thesis? 😀
Comment #73 August 27th, 2017 at 6:58 pm
As Scott says, it was obvious from the beginning that Blum’s paper passed the obvious smell tests that most other such papers don’t. It’s even written in LaTeX for heavens’ sake ;-). And Tardos’s function might be a failing smell test now, but it wasn’t on the list AFAIK in the past.
If it had been posted anonymously, or by the proverbial Roofus McLoofus, would it still have gotten a careful reading by some cogniscenti and had the error or at least the counterexample pointed out? I’d like to think yes, though it may have taken a little longer.
Comment #74 August 27th, 2017 at 7:02 pm
Mitchell Porter,
Did I ever say that my intent is to be generous with incompetent people or that amateurs know more than experts? You are getting all wrong my dear.
I am coming from the vantage point of acknowledging that while the hiring practices of the institutions that employ very smart people definitely make these institutions hire very smart people, at the same time, not every very smart person works at this institutions. And by that token, it would be foolish to create an environment where these smart people who, for one reason or another, don’t follow the traditional path of learned professionals, feel excluded and hopeless to contribute.
Let me give you two examples from the world of computer security and cryptography that have nothing to do with proofs but a lot to do with groundbreaking work. Two of the most important contributions to the world of computer security in the last 10 years have been produced by people who are either unknown or refuse to play by the rules. I am talking of course about blockchain technology, and the signal protocol/app. To this day, the identity of Satoshi Nakamoto remains a mystery and Moxie Marlinspike is one of the most fascinating individuals around. None of these two could have produced their work constrained by the limits of the politics that rule top notch academia or companies like Google.
As Scott pointed out, probably neither Satoshi Nakamoto nor Moxie Marlinspike care much about attempts to shame their work, but what about those like Perelman who do? As I said, I only see down side to this whole “shame attempted p vs np proofs”.
Comment #75 August 27th, 2017 at 7:06 pm
Scott,
“For a second thing, do you have any idea how many “controversial” positions I’d already defended on this blog, before MIT decided to tenure me? Doesn’t that count pretty massively against your thesis? ”
With all due respect, all the positions you have defended in this blog might have been controversial in the world at large, but pretty standard thinking at places like MIT. I get that you were tenured before Donald Trump ever announced that he was running for office, but in an MIT context, the really controversial thing would have been to come out as a strong Donald Trump support, not a Donald Trump basher.
Anyhow, I don’t have much more to add to this discussion, so I will leave it at that.
Comment #76 August 27th, 2017 at 7:10 pm
Re #74 etc, there’s a junior (untenured as of a year or two ago) guy, initials PW (maybe shouldn’t attract searches here), who commented a fair amount on Terence Tao’s blog threads about Polymath8, which lowered Zhang’s prime gap bound to something like 243 in a tour de force of technical machinery. PW himself mentioned being nervous about posting to those thread any mistakes could make him look bad to tenure committees etc.
PW then said he was pleasantly surprised when senior mathematicians who he met at random times complimented him on the nice work he was posting. None of it was earth shattering and he did make some mistakes, but it was a visible contribution that made impressions, so he’s happy now to have done it.
Comment #77 August 27th, 2017 at 7:22 pm
asdf #71:
Why not just update it if and when that happens? No need to take it off the web.
Because if P≠NP is ever actually proved, it will undoubtedly take some time for it to become clear that it was proved—much, much longer than it takes today for it to become clear that (say) Deolalikar or Blum didn’t prove it. Verifying and fixing Wiles’ proof of Fermat’s Last Theorem took 2 years; for Perelman’s proof of the Poincaré Conjecture, 4 years.
Thus, in any such situation, there would necessarily be an intermediate limbo state, when haspvsnpbeensolved.com would be unable to render a confident verdict. (In contrast, by my personal lights, no previous attempt on P vs. NP has ever even risen to that limbo state.)
Comment #78 August 27th, 2017 at 7:29 pm
Another “bolt from the blue” (though now very old) was Friedberg and Mučnik’s independent solutions in 1956 to Post’s problem about Turing degrees, that had been open for more than a decade with various top logicians working on it unsuccessfully. Friedberg was a Princeton undergraduate at the time, and the importance of his work was recognized immediately:
http://www.thecrimson.com/article/1956/2/23/senior-solves-logic-problem-pan-eliot/
The famous letter from Gӧdel to von Neumann that introduced the P vs NP problem, iirc, also contained a lament that someone as mathematically talented as Friedberg was going to study medicine post-graduation, instead of mathematics.
Comment #79 August 27th, 2017 at 7:30 pm
While I’m no fan of racists, Neo-Nazis, or the KKK, the past week has seen some developments in the culture wars between the extreme right and extreme left which make me nervous.
In the last few days, two well-known sites featuring offensive but legal content have been booted off the Internet by their DNS registrars terminating their service, and freezing their domains so they cannot be transferred. Should something as deep in the infrastructure of the Internet as DNS be making content decisions?
Isn’t that kind of like your phone or electric company taking away your service because you expressed an opinion some found unacceptable?
With most important Internet infrastructure in the hands of private companies, which can decline to do business with anyone for any reason, it seems we do not have the same access to newer forms of communication as we did to the legacy versions.
If I hold a left wing rally, and some diehard Communists show up, does that make it a “Communist rally.” Is everyone representing the left at the rally now a Communist, because they “marched with Communists?”
What if the news media keeps showing someone waving a Communist flag as the only image they use when reporting on the “Communist rally,” even though the rally’s organizers specifically asked people attending to not display contentious symbols.
If someone points out this egregious use of “guilt by association,” does it mean they are claiming a moral equivalence between both sides, or saying that the Communists are “fine people?”
There is a free speech rally scheduled in San Francisco by a group called “Patriot Prayer.” An artist has organized his neighbors to go to the venue with their dogs, and leave it covered in dog substance. This is being spun by the press as an extremely light hearted act of completely non-violent protest. I think it’s likely that if any of this dog substance were to end up near a synagogue, our screens would be filled with apoplectic social justice warriors screaming “Hate Crime” at the top of their lungs.
Apparently sauce for the gander is not also sauce for the goose.
Patriot Prayer, by the way, is run by one guy who has denounced racism and white supremacy. It’s stated purpose is to support free speech and the 1st Amendment.
It is a conservative advocacy group, and sometimes, white nationalists will choose to attend a rally organized by them, which is open to the public.
Should the press put “free speech” in quotes when referring to this organization’s purpose. Should they refer to its meetings as “White Supremacist Gatherings?” Should they refer to counter-protesters as “Anti-Hate Demonstrators?”
If the opposition attacks this group during their peaceful rally, for which they have a permit, is the violence the fault of Patriot Prayer? Is anyone saying it isn’t their fault guilty of declaring a moral equivalence between the two sides?
I don’t know the answers to any of these questions, so I thought I would submit them to one of the 10 smartest people on the planet for analysis.
Comment #80 August 27th, 2017 at 7:34 pm
Doh! Looks like Friedberg was a Harvard undergrad, rather than Princeton. Good thing I post anonymously, wouldn’t want to hurt my tenure case ;-).
Comment #81 August 27th, 2017 at 7:35 pm
> Thus, in any such situation, there would necessarily be an intermediate limbo state, when haspvsnpbeensolved.com would be unable to render a confident verdict.
Well it could be like the Atomic Scientists’ Doomsday clock ;-). Or the answer to haspvsnpbeensolved could occasioually shift in and out of states like “hmm, maybe”.
Comment #82 August 27th, 2017 at 7:52 pm
asdf #81:
Well it could be like the Atomic Scientists’ Doomsday clock…
Except that, while the Doomsday Clock remains stuck for decades at 11:58 or whatever, the P vs. NP clock would remain stuck for decades at 12:02. 😀
Comment #83 August 27th, 2017 at 8:35 pm
Larry #79: Those are indeed extremely hard and pertinent questions, a proper analysis of which wouldn’t fit in a blog comment. At the least they merit their own post—alas, a post that I don’t have time to write right now.
For now I’ll confine myself to remarking that, in the specific case of Charlottesville and its aftermath, I think that some of your hard questions weren’t fully engaged. Why not? Simply because the neo-Nazis celebrated the murder of Heather Heyer, in a way that, given the context, seems easy to construe as imminent incitement to commit additional such murders. Indeed, the Heather Heyer angle (rather than, say, the neo-Nazis’ abstract desire for a Judenrein world) was the one stressed in the very thoughtful WSJ op-ed by Matthew Prince, the founder of CloudFlare, agonizing over his non-obvious yet understandable decision to pull the plug on Stormfront.
If we accept that the ideal content-neutral rules that govern the Internet can legitimately be suspended in cases of child porn (or, for godsakes, copyright infringement!!), then certainly they could be suspended in cases of a credible incitement to murder.
Incidentally, this is a criterion that I’m willing to apply universally—also to Communists, Islamists, etc. celebrating a recent terror attack, and dehumanizing its victims, in a way that could be construed as incitement to additional terror attacks in the near future.
I feel more internal discord over the issue of “free speech rallies,” whose organizers explicitly denounce racism and neo-Nazism, and yet which are still targeted by the antifa under the assumption that they’re just neo-Nazi rallies in disguise. For suppose even that the antifa suspicions turn out to be right in various particular cases—i.e., that the “free speech protesters” really are just dogwhistling neo-Nazis. Even so, given the history here, can anyone doubt for a microsecond that a segment of the left would eagerly abuse its newfound power, and start broadening its net to paint any rally that they disagreed with as a neo-Nazi hate rally, against which the most extreme tactics were therefore justified?
In summary, if you want to become an anti-Nazi vigilante—well, I admit that I can’t think of any better kind of vigilante to be! But don’t initiate violence, and try to make really damn certain that anyone you target for doxxing, firing, dog poop, or whatever actually is a Nazi, OK? And to help you ponder the moral complexities involved, maybe watch a few Batman movies.
Comment #84 August 27th, 2017 at 9:29 pm
I share your attitudes towards the ‘lost cause’ narrative, Trump and obviously the nazis and still think the removal of statues as done – by decree and in the cover of night was a poor way to handle this.
Those decisionmakers really should have been the constituents of the universities/localities where those statues are located, as part of a ballot measure, a referendum etc. If there was to be a declaratory value in the removal it is being lost here – the supporters of the ‘lost cause’ can continue to view themselves not just as victims of past victor’s justice but as the silent majority in their surroundings shamed into hiding by the establishment and nothing fuels political growth better than this kind of sentiment – proof by identity of the current white house occupant.
From the NYT article quoting Greg Fenves:
And even though I happen to 100% agree with that – deciding what something represents for other people today and condemning them based on that comes from the same class of intellectual dick moves that you decried in your previous two posts – it is probably possible to hold a noble view of the confederacy without being a slavery-supporting racist – it would be both historically and morally skewed view but that alone would hardly set it apart from most cultural ethoses past and present, trying to deconstruct it in this fashion feels both strategically and tactically stupid.
He goes further to say that the action was explicitly taken in response to the Charlottesville attack which echoes the same normative attitude to governance that got the US the patriot act and the discard of due process whenever the word ‘terrorism’ can be invoked with minimal plausibility and the fact that the US is by no means unique in this sort of power opportunism offers little solace.
[Dis]qualifier: not an American, the little time spent in the US was done in liberal strongholds, maybe the ‘lost cause’ and confederate culture are indeed just a thin veneer for white supremacy today but I really doubt that, more likely it’s a rallying flag in the red-blue culture war but this war is not of the capture-the-flag kind.
Comment #85 August 27th, 2017 at 10:55 pm
Scott #83: There’s a bit of additional context for your statement that “the Neo-Nazis celebrated the murder of Heather Heyer.”
The article that got everyone outraged was published in The Daily Stormer, which is an alt-right parody and trolling website. It is a piece of performance art which exists to provide over-the-top imitation Nazi “news” stories with the intent of making liberals’ heads explode and of deliberately triggering the Internet Outrage Machine.
It is not a bunch of real Nazis, any more than The Landover Baptist Church is a real church, or The Onion is a real news organization.
A typical Daily Stormer headline is something outrageous like “Jews Plot to Destroy Western Civilization by Replacing all Fast Food Workers with Tuberculosis-Infected Somali Rapists.”
Now, it was in extremely bad taste, and totally insensitive to Heather Heyer’s family and loved ones, to use her as the topic of one of its parody pieces, and to say everyone is happy she’s dead because she was a 32-year-old who had not yet reproduced, and therefore served no purpose.
However, I doubt this rises to the level of “imminent incitement to commit additional murders.”
While the Onion is careful to not use actual people for its parody pieces, unless they are public figures, The Daily Stormer is only now learning why that’s prudent policy.
So yes, they screwed up, but that doesn’t mean all White Nationalists are dancing in the streets and cheering her demise. These days, genuine Nazis are considerably more nuanced in their rhetoric.
Comment #86 August 28th, 2017 at 2:37 am
Scott #66: I am interested!
Comment #87 August 28th, 2017 at 4:22 am
tas #21: The argument of the other side (with whom I do not agree) is that there might exist a way of sidestepping the current progress in the field of circuit lower bounds. Also, Norbert Blum was claiming the much stronger P \neq NP over the already-awesome NP not in P/poly.
Comment #88 August 28th, 2017 at 4:53 am
Eno #85:
These days, genuine Nazis are considerably more nuanced in their rhetoric.
I apologize; I was unaware of the existence of the more nuanced, moderate neo-Nazis. (Would those be the ones who advocate at least anesthetizing the Jews before they gas us?) I’ll try to be more careful about that in the future.
But regarding that Daily Stormer piece, and the claim that it’s “just parody,” I feel oddly similar about it as I do about that Piper Harron essay that Sarah Constantin discussed in my previous post—something from the opposite cosmological extreme of the ideological spectrum. Recall: Harron explicitly argued, on an official blog of the American Mathematical Society, that all white males should leave mathematics forever, because they’re taking up space that could be occupied by women and minorities. Recall the awkward position into which that put Harron’s well-meaning defenders: “no, you see, she didn’t literally mean it! She merely literally believes the 5,000 other almost equally inflammatory things she’s said in the same vicinity as that thing.”
Comment #89 August 28th, 2017 at 8:40 am
Maybe you could give some less-harsh results on http://haspvsnpbeensolved.com/
For example;
Don’t count on it
Outlook not so good
Very doubtful
Comment #90 August 28th, 2017 at 10:30 am
Uncle Brad #89 (or whoever did this)
Wow, that is cool. Can you also keep an internal statistics how often it gets used? And maybe even a statistics which URL are checked how often. And if you have all that, try to motivate people to actually use it.
Comment #91 August 28th, 2017 at 10:43 am
Come join me and my fellow members at the P=NP Society on Tuesday night to celebrate this latest total failure in proving P!=NP!
Comment #92 August 28th, 2017 at 10:51 am
Sanketh #87: I think your implications are reversed. NP \notin P/Poly suffices to give P!=NP. P!=NP doesn’t imply NP \notin P/Poly, because there’s still the possibility of a non-uniform family of polyomial-sized circuits computing any problem in NP.
Comment #93 August 28th, 2017 at 10:51 am
fred #91: LOL. Between the SJWs and the Trump supporters, the quantum mechanics deniers and the D-Wave boosters, the P=NP believers and the P≠NP provers, one of these days I’m going to be crushed! 🙂
Comment #94 August 28th, 2017 at 11:06 am
About Trump’s “quasi-defense” of neo-Nazis: Given how unhinged POTUS is that doesn’t surprise me. What does surprises me is that many people on the left are doing something very similar: they quasi-defend neo-Communists. Somehow hammer&sickle, the symbol that represents the atrocities of the 20th century as much as swastika does, is deemed appropriate by many.
I would condemn in the same breath swastika-wearing white supremacists as well as hammer&sickle-wearing promoters of Communism, including Antifa. Would you?
Comment #95 August 28th, 2017 at 11:39 am
Michael P #94: To boil an enormous discussion down to a sentence:
Communism is not quite as bad as Nazism in its fantasized future—which makes it easier to imagine a “decent but deluded Communist” than a “decent but deluded Nazi”—but it’s every bit as bad as Nazism in its empirically-observed past.
So if the antifa counterprotesters were carrying hammer-and-sickle banners (were they?), then yes, that should absolutely be condemned. (That still doesn’t mean that a group chanting “Jews will not replace us” in unison could be said to contain “fine people,” though.)
Comment #96 August 28th, 2017 at 1:05 pm
I had no intention of coming back but then I say this, #94,
“Communism is not quite as bad as Nazism in its fantasized future—which makes it easier to imagine a “decent but deluded Communist” than a “decent but deluded Nazi”—but it’s every bit as bad as Nazism in its empirically-observed past.”
Are we still making excuses for Communism? Not “as bad”? You are a self proclaimed atheist, so perhaps from your vantage point burning churches and slaughtering believers, particularly Christian believers, is not as bad as slaughtering ethnic Jews, but I can see no difference.
Let’s agree that both Communism and Nazism represent the worst that the intelligentsia class has ever produced both in term of theory as well as practice and let’s not make excuses for either one. Otherwise history will repeat itself.
Comment #97 August 28th, 2017 at 1:25 pm
asdf #71, Scott #77: Personally, I thought the “take it down” flourish was the cherry on the sundae that made the joke a lot funnier. From “here is a function that is definitely computable but which I don’t know how to compute” to a mashup of that plus halting problem. Very witty, Wilde.
Comment #98 August 28th, 2017 at 2:32 pm
#96: I’ve taken flak on this blog for writing not only about the horrors of Communism, but about the need for Western leftist movements never to excuse or softpedal those horrors, and to confront their own past complicity in them. I’ve also argued that the Gulag, the show trials, the forced starvations, etc. etc. weren’t mere “implementation bugs,” but were traceable to fundamental flaws in Marxist theory itself—e.g., to Marx’s pseudoscientific and illiberal tendencies; his howling misconceptions about economics and human nature; and his appalling lack of curiosity about how to design political systems that are robust against takeover by tyrants (the problem that had obsessed the American founders a century before him). So again, there’s no need to lecture me on this.
I was careful in what I said. The Communist end-state of universal love and harmony certainly sounds better than the Nazi end-state of all inferior races exterminated or enslaved. But, while that distinction has some minor psychological relevance, it ultimately doesn’t matter that much, because neither ideology ever achieves its end-state: both only achieve millions of corpses in the end-state’s fruitless pursuit.
Comment #99 August 28th, 2017 at 3:25 pm
As a long-time reader of this blog, let me once again express my admiration. Your patience with comments is admirable. I’d get very tired of having to re-state, over and over again, that I’m not a horrible human being, and that being able to distinguish between degrees of awfulness is not the same thing as endorsing any of the awfulness. That you’re not in a continual Heffelump Grump (courtesy a gem from my children) is remarkable.
Comment #100 August 28th, 2017 at 4:00 pm
Scott 95 & 98:
Apart from the Marxist fiction, the realities of Nazi and Communist states are very similar; we have agreed on that *here*, I believe.
The reason neo-Communists concern me more than neo-Nazis these days is precisely the attractiveness of Marxist fiction to so many people. Recall that Nazis came to power on anti-Communism platform: they identified the real evils of Communism and rallied people against it (and added national supremacy and persecution of Jews). I am afraid that pro-Communism groups in US are going to do pretty much the same thing in reverse: identify the real evils of white supremacy and rally people against it (and add political correctness and persecution of those who dare to disagree).
Notice how eager the left is eager to jump on anyone arguing in favor of Free Speech. There have been live banners and FB messages floating around that proclaimed: “Free Speech = Hate Speech”. There are some polls you can google that demonstrate that large and increasing percentage of students favor political correctness over free speech. There are totalitarian tendencies spreading around in US, and more so from the left than from the right.
Therefore I find it very important to simultaneously condemn both extremes and highlight the actual similarities between them.
Comment #101 August 28th, 2017 at 4:38 pm
Nilima #99: Thank you so much.
Comment #102 August 28th, 2017 at 4:45 pm
Scott #98,
Thanks for your clarification. At the same time Michael P. #100 makes very pertinent observations that I agree with.
Nilima #99,
I can assure you I am smart enough to distinguish between degrees of awfulness. My point is that I don’t see any meaningful difference when it comes to awfulness between Communism and Nazism. The one Scott refers to in #98 seems to me so small, like 10^(-1000) small that I don’t know if he thinks that some of us are stupid or he really believes it is worth giving too much thought to it. The problem with spending time debating these meaningless differences, Cipolla would have told you, is that you trigger the idiots among us to believe that indeed, these differences are so meaningful that it is not so bad after all to be a Communist, at least not as bad as being a Nazi.
I am sorry, as a free thinker I have as little patience with those who say “Nazism was bad, but” as with those who say “Communism is bad, but”. For starters, real Nazism, the one that believed in the supremacy of the state to impose its national socialist agenda first in Germany, then in Europe as a whole is gone for good. Real Communism is still with us in Cuba, in North Korea and a bit less so, but still dominant, in China. The losers that call themselves “neo Nazis” are a bunch of Cipolla-idiots that would have been exterminated by the real Nazis if they were still with us.
Comment #103 August 28th, 2017 at 6:34 pm
#102: The distinction matters, I think, only for the limited purpose of judging individuals.
If someone tells you they support Adolf Hitler’s vision for the world, it doesn’t really matter what “nuance” they try to add later (e.g., that they would’ve preferred deportation to Madagascar as a solution to the “Jewish Question”)—it’s safe to assume the person is thoroughly evil.
By contrast, if someone tells you they support Karl Marx’s vision—not, of course, the later perversions of it by Stalin and Mao and Pol Pot, but only the “true original vision,” which is yet to be realized anywhere—the possibility could be entertained that the person is merely naïve and deluded and needs to learn more.
One difference, again, is that the Marxist fantasy is less inherently obscene than the Nazi fantasy, and if we’re only trying to judge a deluded person’s moral character, then the reality (i.e., equally horrific for both systems) matters less than whatever fantasies fill the deluded person’s head.
But now that I think about it, an even bigger difference might simply be historical contingency. Hitler lived to carry his vision to its externinationist conclusions—leaving no doubt for even the densest, most ill-read person alive today about what the vision actually consisted of—whereas Marx didn’t.
Comment #104 August 28th, 2017 at 6:56 pm
Scott #103,
You are making my point. When you speak of Karl Marx “true original vision” you are being ignorant (this is where I am leaning to) or malicious.
Let’s speak of Karl Marx “true original vision”. His words, not mine,
https://en.wikipedia.org/wiki/Dictatorship_of_the_proletariat#Karl_Marx
…commenting on revolution in Vienna he again highlighted the role of the violence: “there is only one way in which the murderous death agonies of the old society and the bloody birth throes of the new society can be shortened, simplified and concentrated, and that way is revolutionary terror”
This is pretty unambiguous. The “true original vision” of Karl Marx included the use of political violence, what he called, “revolutionary terror” to achieve the goals deemed necessary. Mao, Pol Pot and in fact every single Marxist organization I am aware of (FARC, the different “Red Armies” that terrorized Europe in the 1970s, https://en.wikipedia.org/wiki/Left-wing_terrorism#Europe) all ma(k/d)e the use of violence to achieve goals part of their belief system.
Who was(is) the target of this political violence for Marx and his followers? Anybody who, for whatever reason, disagre(s)ed with Karl Marx’s “one true vision”. We see that today with those who want to criminalize as “hate speech” what is uttered by those who say things they don’t like.
It’s like saying, oh gee, I love that Nazi German society for all the intellectual breakthroughs it produced. In fact all leading German intellectuals of the time, such as Heisenberg, were Nazi Party members or Nazi sympathizers. Many -I don’t have numbers to discuss but using support for eugenics as an indicator we can say that a lot- American intellectuals were also staunch Nazi supporters, including JFK http://www.bbc.com/news/world-us-canada-39371715. That pesky hatred for Jews, Gypsies, gays, disabled https://en.wikipedia.org/wiki/Aktion_T4?, minor stuff. Look at the astonishing intellectual feats it produced and it would have produced had it not been stopped by the Allies in WWII. This reasoning is pure garbage and so is, with all due respect, your reasoning surrounding the “true Marx ideal”.
Comment #105 August 28th, 2017 at 7:17 pm
Scott #103,
One more thing. I have had this debate about the “true original vision” with many Marxists in the past (I am not saying you are one, but you are certainly echoing their talking points beautifully). These debates is why I know it is based on a false historical premise. Marx’s “true original vision” included the use of violence to annihilate anyone who opposed his other ideas.
It always astonishes me the effectiveness of Marxism in brainwashing its followers or those who rationalize its abuses given that paradoxically, these same followers seem to be very numerous in institutions of higher learning. Thus, I prefer to give rationalizers the benefit of the doubt, and assume they lack historical knowledge about Marx, than assume malice on their side.
Comment #106 August 28th, 2017 at 7:31 pm
Scott #103,
And something more. Let me see.
Nobody “misinterpreted” Mohadma Ghandi’s “non violent” vision.
Nobody “misinterpreted” Martin Luther King’s “non violent vision.
Nobody “misinterpreted” Mandela’s “non violent” vision once he abandoned the violent Marxist approach.
You analysis, other than historically inaccurate, doesn’t make any sense. Every single follower of Marx that has attempted to apply his ideas has used political violence early in his movement, as an instrument to achieve their other goals.
So Scott, perhaps it is time to admit that you have been conned by Marxist propagandists.
Comment #107 August 28th, 2017 at 8:54 pm
Eden #91: Yup! Thanks for correcting me. I seemed to have gotten confused. On the other hand, we do not believe NP in P/poly either because it would collapse PH.
Comment #108 August 28th, 2017 at 11:36 pm
And sorry for yet another post. Feel free to construct a single comment with all my feedback.
The Communist manifesto, while not technically the work of Marx alone, but rather, joint work with Friedrich Engels -whose support for political violence in unquestioned- finishes by saying
https://www.marxists.org/archive/marx/works/download/pdf/Manifesto.pdf
“The Communists disdain to conceal their views and aims. They openly declare that their ends can be attained only by the forcible overthrow of all existing social conditions. Let the ruling classes tremble at a Communistic revolution. The proletarians have nothing to lose but their chains. They have a world to win.”
You can play all mental gymnastics of the world you want, but it is pretty hard to make a case that “pure Karl Marx” explicitly excluded the use of political violence against those who got in the way either during the process of achieving the “Marxist utopia” -what Marxists call the revolutionary process- or after the utopia has been achieved -as it is the case now in Cuba or was the case in the Soviet Union.
The use of violence in the pursuit of the Marxist ideal, and after the ideal has been achieved to crush the dissidents. is not a bug or an unintended consequence of Marxism. It is a feature of “pure Marxism”.
Comment #109 August 28th, 2017 at 11:45 pm
#104-#106: God dammit, you were so revved up to call me conned and naïve that you didn’t even read my comments enough to see that I already agreed with you.
Marx might not have understood how his anticipated bacchanal of revolutionary violence would lead not to an omelette but to a field of eggshells, but in any case the problems with Marxism go all the way back to the source; it takes considerable whitewashing or ignorance to believe otherwise.
Comment #110 August 29th, 2017 at 12:00 am
Scott #108,
Then I don’t understand. Let’s put it in mathematical terms.
Assume there exists a norm, A, so that A(something) is an absolute measure of how awful something is. A follows all the properties of a norm: https://en.wikipedia.org/wiki/Norm_(mathematics)#Definition .
My contention is,
A(Nazism) = pretty big number 1.
A(Communism) = pretty big number 2.
|A(Nazism) – A(Communism)| < epsilon
With epsilon pretty big number 2 or vice-versa? I don’ t get it.
It must be one of those academic things: https://en.wikipedia.org/wiki/Sayre%27s_law “In any dispute the intensity of feeling is inversely proportional to the value of the issues at stake.”
So if we agree in the above formulation, then I don’t have anything else to add.
Comment #111 August 29th, 2017 at 12:11 am
Larry and Scott,
It is impossible to deal with all the nuts out there.
Usually most of us can afford to ignore fringe nuts on the right and left edges. However, at this point in time, there are a LOT of right wing nuts. Supposedly around 20% back Trump no matter what. Meanwhile, the left wing nuts, social justice warriors, etc., are about 1/100 of a percent, so we can mostly continue to ignore them.
I doubt if there are all that many nazis out there, but there are plenty of white racists, so this branch of right wing nuts is truly something to worry about.
Comment #112 August 29th, 2017 at 12:24 am
Raoul #111:
Meanwhile, the left wing nuts, social justice warriors, etc., are about 1/100 of a percent, so we can mostly continue to ignore them.
Alas, not if we live in academia, in which case we do indeed have to worry about both kinds of fanatic: the kind that’s stronger, scarier, and more numerous in the wider world, and the kind that’s so in our own local environment.
Comment #113 August 29th, 2017 at 12:51 am
#110: I completely agree with you about A(Nazism) and A(Communism) both being enormous. But as for
|A(Nazism)-A(Communism)|
being less than ε, the problem is that my internal awfulness-meter only lets me approximate log(A(Nazism)) and log(A(Communism))—so it’s not precise enough to address such questions about finely-tuned cancellations.
(Coming full circle, this actually directly relates to Stuart Kurtz’s work on the complexity class GapP and my talk about it, mentioned at the beginning of the post!)
Furthermore, the point at which you ask me such detailed questions, is precisely the point at which I start insisting on distinguishing the different varieties of awfulness, rather than collapsing them all into a linear metric.
Comment #114 August 29th, 2017 at 8:40 am
Empirically, a huge percentage of early and even not so early 20th century intelligentsia were either communists or somewhat sympathetic to Communism. Apparently, it was easy to ignore the violent means needed, or maybe it was deemed that violence would turn out to be manageable to achieve the goals (“the goal justifies the means”).
In fact, people don’t forswear violence to achieve their goals even today – we have such concepts as justified violence (the State’s prerogative), Just Wars etc. So, Communism’s final goal of building a just society was, without the benefit of a decades-long hindsight, pretty attractive to a lot of good people.
And regardless of the particulars of Marx’s/Lenin’s/Trotsky’s/Stalin’s/Mao’s visions on how specifically to achieve this, one could imagine people gravitating towards Communism voluntarily (not that it happens on Earth, but it could in principle, maybe on Alpha Centauri.) That’s a distinction worth having between Nazism and Communism.
Comment #115 August 29th, 2017 at 9:01 am
A tangential question, inspired in part by Blum’s attempted proof that NP != P/poly, and the observation that if NP is contained in P/poly then in fact NP is contained in P/poly then NP is contained in P/polyspace were P/polyspace is P/poly with the advice restricted so that it is a function computable in PSPACE.
As of right now, it seems like the only serious direction that has a substantial hope of resolving P != NP is geometric complexity theory. However, even that seems very far off. It seems that the basic idea of the program is to first show that that VP != VNP (a more natural statement in GCT), and then show that show that VP ! = VNP implies that P/poly != NP/poly. But it isn’t at all clear that P/poly != NP/poly implies P != NP.
A potentially more natural thing to look at rather than P/polys and NP/poly is these same classes but where the polynomial length advice is restricted to being computable in PSPACE, that is whether NP/polyspace is contained in P/polyspace. It seems like even proving that NP != P with both the assumptions that 1) NP/polyspace != P/polyspace and 2) NP/poly ! P/poly is still very difficult.
In this context, the question is is there some reasonable, non-trivial restriction on how much computation the advice producer is allowed where having NP and P not equal with that amount of advice would prove that P != NP? Obviously, one could get trivial results by say restricting the advice builder so that it only had a polynomial amount of time for computing the advice or something silly like that. Can we do something non-silly?
Comment #116 August 29th, 2017 at 9:14 am
Scott #113
If you insist… I further contend that
log(A(Nazism)) is very big number 3
log(A(Communism)) is very big number 4
And that |log(A(Nazism)) – log(A(Communism)) | is still infinitesimally small.
Meaning, even if we are talking only about the exponent, irrespective of the base you express the log, we are talking of such a big awfulness of both, that entertaining discussing the nature of the epsilon, whether on a linear or a log scale is irrelevant.
Here is another way of looking at it. Suppose instead of using the norm metaphor, we use the cardinality metaphor to express the awfulness. I contend that
|Nazism| > 2^(aleph 0)
|Communism| > 2^(aleph 0)
So we are talking of a degree of awfulness that is at least commensurate with the cardinality of the real numbers. I suppose that from a strict academic sense, it might make sense to consider the above question, but in real life, it doesn’t make any difference whatsoever and engaging in a practical discussion of which one is worse, inevitably leads to bad outcomes for those who engage in such discussion.
Take for example the self proclaimed “neo Nazis”. Suppose that through a series of inexplicable events, the real Nazis were able to achieve power in the United States in our lifetimes. These “neo Nazis” would be the first to go through the gas chambers. After all, few people know that before the Nazis went after the Jews, Gypsies and other undesirables, they went after those the Nazis determined to be non productive members of society to test and polish their mass murder tools. That’s what Aktion T4 was all about. Losers like the Charlottesville killer would be part of the first batch of those exterminated for the glory of the Nazi United States.
Comment #117 August 29th, 2017 at 9:50 am
With respect to: haspvsnpbeensolved.com
Why not a list of (intellectually honest attempts but otherwise) failed p vs np papers and a brief synopsis as to why the paper is wrong? It seems like your blog probably has 90% of the information already needed for this sort of thing and I bet you can find some volunteers to pick through to find all the details of past papers already discussed.
Comment #118 August 29th, 2017 at 12:05 pm
Peter D #114
I have another comment explaining why I believe entertaining these differences is a futile exercise in a practical sense, so I won’t get into that.
What I want to argue is this,
“a huge percentage of early and even not so early 20th century intelligentsia were either communists or somewhat sympathetic to Communism”
That was probably true in the humanities, but in the sciences, a huge percentage were actually Nazis or Nazi sympathizers. While we know the side of the story of those, like Einstein -and other Ashkenazi Jews-, who fled Nazi Europe, there is also the story of those European scientists who not only stayed despite reservations with respect to Nazism-like Niels Bohr- but who -like Heisenberg or Wernher von Braun ,whom the United States owes its space program- that were happy Nazi collaborators.
This sympathy with Nazi ideas among the intelligentsia of the hard sciences didn’t end with World War II. William Shockley is the most visible exponent of sympathy to Nazi ideas in the second half of the XX-the century, but the most you can say about him is that he didn’t care about being vocal about his ideas. He was not the only one who contributed to https://en.wikipedia.org/wiki/Repository_for_Germinal_Choice .
So please, let’s stop this notion that the intelligentsia are all well intended people who were conned by what they perceived could be the good outcome of Communism. They weren’t. Those favoring Communism over Nazism did so because they probably say themselves at the top of the pyramid -like some scientists were in Communist Russia- had the Communist goals been achieved. An in general, it is my personal experience that intelligence and ethics are orthogonal qualities. Scoring high on one of them does not necessarily imply scoring high on the other one.
Comment #119 August 29th, 2017 at 12:25 pm
Let’s throw Fascist Italy and Imperial Japan in the mix as well!
Comment #120 August 29th, 2017 at 1:57 pm
#118: I think it’s fair to call Shockley a racist and an asshole, but I don’t think it’s fair to call him a Nazi—particularly since he was apparently a spectacularly effective operations research manager fighting the Nazis during WWII.
Comment #121 August 29th, 2017 at 2:00 pm
TPWG #110: Glad to see you are learning about normed linear spaces, one of the truly fundamental ideas in science.
But I think you are going to have trouble proving that a norm exists on the space of nut case political theories.
If you can construct such a norm, please let me know, because some of my research involves extending norms to more general spaces, and I might be able to work with Complex nut case political theories. An imaginary dimension would be cool.
Comment #122 August 29th, 2017 at 3:03 pm
Scott #120
I can’t believe a man of your intelligence said that, specially since you recently wrote an entire entry justifying why Kolmogorov never publicly confronted Communism nor Stalin.
The entry of the United States in World War II was a complex affair. It was not an idyllic crusade of the free world against the Nazis since what happened is that in fighting the Nazis the US picked what it perceived the worst of two very bad options (the two totalitarian options we have discussed here) when decided which side to be on. Then the United States spent 40 more years fighting the Soviet Union on intellectual and defensive -by way of nuclear testing- grounds. Shockley probably didn’t have any choice but to join the war efforts when called to do so.
In addition, in Shockley’s case, we don’t have to make any assumptions. He made his Nazi-like views pretty clear during his lifetime in interviews and debates like this one https://www.youtube.com/watch?v=V-9jtRx5iGk . Not only he made racist arguments, but one of his best known proposals was a dysgenics program that would have paid blacks to undergo voluntary sterilization. Shockley was a very smart guy so if he didn’t propose an outright Nazi agenda is because he probably knew too well that he would have become even more ostracized than he already was in the 1970s.
Comment #123 August 29th, 2017 at 3:12 pm
Raoul Ohio #121
Good that you are an expert on norms. Please, work out my cardinality metaphor and see if you can come up with a meaningful way to use a log argument to make the Nazism/Communism difference work. Hint: it has to do with how multiplying aleph 0 by any number (such as the base of a log) still gives you aleph 0.
Comment #124 August 29th, 2017 at 3:15 pm
Joshua #115: No, if P=NP, then P/poly=NP/poly. To see this, given a language L∈NP/poly, let M be a nondeterministic TM that decides L with advice strings an. Then let L’ be the set of pairs of the form (x,a) (i.e., input and advice) that M accepts. Clearly L’∈NP. So if P=NP, then L’∈P. But that means in particular that L∈P/poly.
Comment #125 August 29th, 2017 at 4:28 pm
Ah, TPWG, find me one, one! disillusioned Nazi-sympathizer of Bertrand Russell stature and I’ll concede your point. But as I see it, there were a lot of genuinely good people who believed or at least hoped that Communist experiment could yield a just society, while there was no one similar on the Nazi side. Scientific/engineering-only luminaries don’t count, as their stature has nothing to do with ethics. Show me philosophers/intellectuals/writers who are respected for their views now and who at any point in their lives supported or were sympathetic to Nazism but then got disillusioned.
Comment #126 August 29th, 2017 at 5:37 pm
The problem with gatekeepers #122: In your opinion (I’d be interested in Scott’s as well), what’s the difference between a racist/white supremacist and a Nazi? Do you believe all white supremacists are Nazis? Do they only count if they self-identify as Nazis, carrying around swastikas and the like? Or is there there some middle-ground acid test that distinguishes some people as Nazis?
Comment #127 August 29th, 2017 at 6:59 pm
Dan #126: The fact that the Nazis had their one specific time in the sun—and that they used it to make it so horrifically crystal-clear who they were and what they stood for—makes your distinguishing problem easier than it would be otherwise.
If a racist / white supremacist expresses any sort of admiration for Hitler, the Third Reich, or specifically the Nazi extermination of Jews and other undesirables: fair to call them a Nazi themselves. (I’ll also put Holocaust deniers into this category—since famously, and paradoxically, the brain-damaged notion that the Holocaust never happened almost always functions as just a convoluted way of saying that it should have.)
If, on the other hand, a racist / white supremacist explicitly condemns Hitlier and the Final Solution: well, OK, they might still be racist or white supremacist, but unlike much of the modern left, I’m not going to use the word “Nazi” for absolutely anyone whose views I find abhorrent. So for example, I’m perfectly able to distinguish someone who wants to kill all Jews from someone who merely wants to rough them up, or take their money, or bar them from universities, or force them all to live in Israel, or force them all to leave Israel, and who stops there.
If a racist / white supremacist refuses to say one way or the other what they think about Hitler and the Final Solution, or offers slimy equivocations, then it’s safe to assume they’re a “closet Nazi” according to this scheme.
Comment #128 August 29th, 2017 at 7:57 pm
Peter D #125
I reject the premise that Bertrand Russell is somebody whose opinion on what’s good or bad is important to me. He shared with the Communists a vision of a society without religion. As a Christian believer, I definitely don’t think such a world is a good idea. Surely, Russell was probably willing to give the Communists a pass initially despite the fact it is unquestionable that Karl Marx’s original vision included the use of political violence to reach the goal of an atheist society. Many contemporary people in the humanities had a better moral compass than him. I understand that Bertrand Russell is some sort of demigod among the atheistic intelligentsia but you have to understand too that outside that world, he doesn’t enjoy much respect beyond his work as logician. If you want a contemporary reference who had all figured out with respect to both Communism and Nazism, read the work of Tolkien in his capacity as public intellectual. He didn’t need to see empirical horrors to despise both Communism and Nazism. Even among today’s atheistic intelligentsia you have better guides than Russell. You don’t have to be a Christian to reach the conclusion -that escaped Russell- that Jurgen Habermas reached that the Western values of equality, love and justice do not come from Karl Marx but from the Judeo-Christian tradition. More here https://en.wikipedia.org/wiki/J%C3%BCrgen_Habermas#Religious_dialogue .
To summarize, I think your question is ill-posed and I stand by my point that the world of intelligentsia of the first half of the XX-th century -which included the hard scientists and engineers you want to exclude- was filled of very sick people, intellectually speaking. There were both Communists and Nazis among them, and I do not respect the personal option of embracing either from these intellectuals. I still respect their work in their respective areas of expertise -such as Shockley’s invention of the transistor- but do not have to respect them as human beings.
Comment #129 August 29th, 2017 at 8:25 pm
Dan Staley #126
My definition of Nazi and white supremacist is the same as Scott’s on #127.
I want to clarify one thing though. I do not consider the labels “Nazi” and “neo Nazi” to be equivalent. With “neo Nazi” we are talking about a bunch of losers, like the Charlottesville’s killer, who perpetrate or threaten to perpetrate randoms act of violence which, sometimes as in Charlottesville, result in murder. As horrific as these acts of violence are, I have personally nothing to fear from neo-Nazis in 2017 America. I know where they are or where they threaten to be with one of their farcical demonstrations and they are easy to avoid.
For a contemporary version of “Nazi” thinking, I would point to people like William Shockley or James Watson. These two go beyond white supremacy. If people like them every gained political power, they would enact Nazi policies like those we saw in Nazi Germany but perhaps using more sanitized ways, such as high bonuses for people to go voluntary sterilization, abortion -as Iceland is doing to eliminate Down Syndrome people http://www.torontosun.com/2017/08/27/why-are-we-trying-to-eliminate-people-with-down-syndrome – or euthanasia to ensure that only non-undesirables populate the Earth. Nazism is at its core social Darwinism, ie, the survival of the fittest. I definitely fear these “Nazi” thinkers way more. And if you want to find them, all you need to do is to attend a high profile academic conference or meeting that includes members of NAS or NAE and pay attention to what they say when they believe that they are talking among themselves and nobody else is listening. To be clear, I am not saying that all academics are Nazi or that all NAS/NAE members are Nazi, only that you are more likely to find Nazi sympathizers you should be afraid of among them than among the so called “neo Nazi”.
Comment #130 August 29th, 2017 at 10:01 pm
@tpwg#116- Aktion T4 was targeted at people that had specific illnesses, not at “losers” in general. Although many of the “asocials” sent to the camps were “losers”.
Comment #131 August 30th, 2017 at 3:56 am
Gatekeepers #104,
I haven’t read any Karl Marx but Thomas Jefferson wrote stuff like “The tree of liberty must be refreshed from time to time with the blood of patriots and tyrants”. Sounds kind of similar. Question is what kind of society you want to end up with afterwards. Also now that we have the internet, maybe instead of bloodshed we can just type in all caps when we get angry.
Comment #132 August 30th, 2017 at 4:46 am
This P!=NP paper from 2017 contains a nice reference section of P vs NP proofs which actually managed to get published in some seemingly serious journals, like IEEE Latin America Transactions. The proof itself is of course wrong, but the introduction is funny and contains gems like the quote
It was published in the proceedings of some conference on page 170, but have a look at page 22 for a special laugh.
Comment #133 August 30th, 2017 at 6:07 am
DLI #117:
Why not a list of (intellectually honest attempts but otherwise) failed p vs np papers and a brief synopsis as to why the paper is wrong?
Gerald Woeginger already has a webpage that functions as a “graveyard of wrong P vs. NP solutions,” so that would be the obvious starting point to create what you wanted.
Among experts, I’m guessing that you’d find roughly as much enthusiasm for curating this list as you’d find among NASA JPL engineers for curating all the different designs for interstellar spacecraft that kids have drawn wth construction paper and crayon. (So in particular, probably a nonzero amount!)
Comment #134 August 30th, 2017 at 7:40 am
Scott #133
but interstellar spacecrafts at least can be built and they either fly or they don’t!
Comment #135 August 30th, 2017 at 8:19 am
Scott # 124,
Doh! I was going off of https://cstheory.stackexchange.com/questions/529/does-vp-neq-vnp-imply-p-neq-np which claimed that P/poly != NP/poly didn’t immediately imply P != NP, but your logic shows that it does. So my entire question is uninteresting.
Comment #136 August 30th, 2017 at 8:55 am
TPWG #118: At the very least, you are wrong about Heisenberg. Read this: http://www.nybooks.com/articles/2016/12/22/private-heisenberg-absent-bomb/
Comment #137 August 30th, 2017 at 11:05 am
Arko Bose #136
Look, I get one thing, and that is, that for people who worship intellects (I know, I have a past life as intellect worshiper too) it is very hard to accept that somebody can be a very brilliant mind and be immoral. As I mentioned above, my current thinking is that these two qualities are orthogonal (and I would say even continuous, not discrete). In the bivariate graph (intellect, ethics) you can find all sorts of people, and that’s OK because human beings are complicated. Even Einstein -who is generally portrayed as the best of both- was at the very minimum an avowed adulterer, and some would even say a bad father to his children, although the latter is still under contention.
I see the reference you mention as an attempt to clean Heisenberg’s legacy. These are draft letters that Bohr never send describing his side of the story that your article refers to,
https://www.aps.org/publications/apsnews/200208/viewpoint-seitz.cfm
“While we do not know full details about their discussions, the record makes it clear that Heisenberg brought up – in what appears to be a heavy-handed way – two issues that were guaranteed to raise Bohr’s ire. Since German victory in the war now seemed assured, Heisenberg suggested that Bohr takes steps to promote friendly relations between Denmark and Germany. Bohr could only have been incensed at the proposal. He was a very loyal Dane, a notable distinguished father-figure in his country, and he well knew that his fellow citizens were outraged by the German occupation. The notion that Bohr would support any official form of friendly relationship was simply beyond comprehension under the circumstances. On the more personal side, Bohr was partly Jewish and must have despised the German leadership for promoting the anti-Semitic Nuremberg Laws.
In a similar manner, Heisenberg stated that he and a group of colleagues were in the process of developing a nuclear chain reaction based on the fission of uranium. If we can trust Bohr’s memory a decade and a half later, Heisenberg implied that he had a fairly complete understanding of the steps needed to achieve such a reaction, but would not go into details. He also stated that work of this kind would ultimately lead to the development of some form of nuclear bomb that would probably play a crucial role in bringing the war to an end if they succeeded. He could not at that time have realized how fully prescient he was, since the Pacific war was far away and the US was not yet engaged. Clearly such an admission would have angered Bohr at least as much as the proposal that he cooperate with the existing German government.”
Who do you believe? Based on everything we know about how cozy not only many German scientists, but many prominent German intellectuals, had been with the Nazi government, I believe Niels Bohr.
After World War II was over there was a great effort from many former Nazis to clean their past and I see what you bring up as part of that effort.
I remember when I first learned about Nazi Germany in high school, I just saw it as part of something I had to know by heart to gain a good grade in my history class. Years later, like in my 20s, when I began to think deeper about these issues it seemed incomprehensible to me that anything of that sort could have happened. We are all “good people” after all. I never had a “negationism” phase, but I did have a skeptical phase with the official version of the events I was told because, after all, history is always written by the winners. Then, in my early 30s, I stumbled into this documentary https://en.wikipedia.org/wiki/The_Nazis:_A_Warning_from_History in Netflix (I watched all episodes of it). Everything that the official history tells about Nazi Germany is true, including that most Germans were completely oblivious to the suffering of the Jews and other undesirables. We should not fall for any attempts to minimize or sanitize what happened there. It was humanity at its worst and there is no other way to see that. Heisenberg was not the Oskar Schindler of Nazi Germany’s nuclear program.
Comment #138 August 30th, 2017 at 11:21 am
Hi Scott,
If you could you tolerate another “good naive commies” discussion, I’d like to challenge the assertion that they exist. If I understood you correctly, you distinguish Nazis from Marxists in that Nazi vision of ideal future is inherently abhorrent while Marxist vision is not, so one can imagine a nice person who is not familiar with the history of Marxist regime, never read Marx, but supports Marxism based solely on the proclaimed vision of the ideal future it promises.
I think you completely misinterpret what drives modern Marxist: it’s not charity, it’s *envy*, an instinct as base as the hate that drives Nazis. Here’s a glimpse into that: “Millennials … Prefer Venezuela’s Food Lines Over America’s Income Inequality” http://www.dailywire.com/news/20027/watch-woke-millennials-say-theyd-prefer-venezuelas-james-barrett
They don’t want to improve the life of poor, they want to make sure that nobody is better off than them.
There is a joke about the devil offering a person whatever he wanted under one condition: the person’s neighbor would get twice more. And the person asks for a semi-fatal heart attack. This is what Marxist envy is: you don’t want a society that’s better off on average or better off for the poor; you want to make sure that nobody sticks out, and that’s more important than anything yet.
Here’s one of the jokes I’ve heard as a child back in USSR:
The Devil inspects the Hell and sees that one of frying pans is not guarded. “Why don’t they escape?” – he asked. “These are Nazis, they were ordered to sit there and nobody dares to disobey.” – was the answer. The Devil proceeds and finds another unguarded frying pan, and here’s the explanation: “These are the communists; whenever somebody is trying to escape the others pull him back.”
I’ve got to add that IMO the root of the problem, although extreme in Marxist minds, is also present in mainstream American left: it’s prioritizing equality over prosperity. Democrats are hammering the idea that equality trumps everything for quite a while. Marxist took that a step further by asserting that equal misery is better than unequal prosperity. And that step further is in my eyes is inherently evil.
You probably heard the horrible story about a former chimp owner who got brought a birthday cake to the place where chimps were kept. Alas, there wasn’t enough cake for *all* chimps there, so he got most viciously attacked:
http://articles.latimes.com/2005/mar/05/local/me-chimp5
Why did the chimps attack somebody who brought some of them a cake? He didn’t take anything away from them. The answer is obvious: in the eyes of the chimps he did take something away from them: he decrease the amount of equality in the group.
But these were just chimps; would people wouldn’t behave like that, even equality-prioritizing Marxists? Alas they would, and they did. Russian and Chinese revolution proved that. And here’s a quite hilarious case of chimp-like behavior from 2017: a baker in Russia decided to help poor by distributing bread for free in his home town. Alas, there wasn’t enough bread for everybody. The enraged citizens verbally assaulted him and filed complains at the city hall.
http://informat.com.ua/shhedryj-pekar-razdaet-hleb-besplatno-i-dorogo-za-jeto-platit/
25 years after the fall of Russian communism, but equality-worshiping Marxism is still strong in the hearts of many.
That’s why I find it necessary to challenge the assumption that good naive Marxists exist. No, they don’t: Marxism implies extreme envy, and that’s incompatible with niceness.
Comment #139 August 30th, 2017 at 11:49 am
Arko Bose, wow, thanks for that link! If true, this casts Heisenberg in a completely new light!
Comment #140 August 30th, 2017 at 12:11 pm
“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… ”
You seem to have a quite “healthy” and open approach to sexuality, kudos! 😉 Just don’t get arrested for public indecency 😉
Comment #141 August 30th, 2017 at 3:45 pm
I bet $200,000 P vs NP is not resolved until after there is a mobile version of Shtetl Optimized 😉
Comment #142 August 30th, 2017 at 7:28 pm
Peter D #139
Don’t fall for the scam. Here is a more detailed discussion on the topic https://history.stackexchange.com/questions/8491/did-heisenberg-undermine-the-german-atomic-bomb-by-deliberately-hiding-his-exper most see the sanitizing attempt for what it is.
I have spend a lot of time studying what happens in totalitarian societies, and the result is inevitably the same -sadly. We want to think, as William Shockley defended in the video above to justify his own Nazi-like ideas that he tried to differentiate from Nazism policies- that if people knew what was going on, there would be an uprising that would get rid of the totalitarian ruler. That’s not what usually happens, whether you look at Nazism, Communism (if you have dual citizenship, you could try to sneak in Cuba to get an idea), Serbian regimes, etc. In these situations is every person for himself/herself and the elites behave no differently from average Joes: the overwhelming majority comply with the totalitarian regime inventing rationalizations for their compliance, and then you find a couple of heroes here and there like Oskar Schindler.
You think you would behave differently? Think again. I hope people are familiar with the Milgram experiment. More info here https://en.wikipedia.org/wiki/Milgram_experiment
If you think that that was then in the 1960s, and now is now, think again. There have been several renditions over the years, here is a pretty recent one https://www.youtube.com/watch?v=y6GxIuljT3w , and the result is always the same. Most people rather obey authoritarian figures than risk negative repercussions for opposing what is objectively a moral wrong.
That’s who we are. Christian theology calls this feature of humanity “original sin”. You can call it whatever you want to call it, but human beings are not angels.
Comment #143 August 30th, 2017 at 9:15 pm
BTW, this is where you can watch the documentary I mentioned,
https://topdocumentaryfilms.com/the-nazis-a-warning-from-history/
It includes testimony of actual Nazis who were alive at the time the documentary was made (late 1990s) who confirm everything that happened. Some are not even remorseful.
Comment #144 August 31st, 2017 at 12:25 am
#137: I agree that, in my own life, I haven’t observed any clear correlation between intelligence and “moral goodness,” with all four corners of the plane densely populated. At the least, if there were a correlation, it would take a social scientist to tease it out.
On the other hand, I submit that there’s a second quality, which is just as important for success in science as raw intelligence is, and which could be summarized as: openness to new ideas, willingness to listen to opposing arguments (and to separate the arguments from people), willingness to let empirical reality override your preconceptions, willingness to consider the possibility that you were wrong and to admit as much. And this second quality is not only strongly correlated with moral goodness as I understand it; I even consider it to be part of moral goodness.
Of course, there can exist situations where A and B and correlated and B and C are correlated even though A and C are not. This might be the case with the triple (intelligence, openness, moral goodness).
Comment #145 August 31st, 2017 at 1:45 am
TPWG #137: I grew up with a firm notion of resentment towards Heisenberg, too. But recent revelations seemed to shed more light on the issue that made me wonder if there was more to it than I believed I knew.
These are all historical events, and short of getting everything on videotape, every account is open to scrutiny and skepticism.
Speaking for myself, I have not been able to convince myself which account is clearly a “scam”, just because it did not strengthen my own confirmation bias.
Comment #146 August 31st, 2017 at 2:07 am
Also, the new revelations come from Heisenberg’s private letters that he and his wife exchanged during that time. All of that correspondence has been published in the book My Dear Li (https://www.amazon.in/dp/B01L7SSCNU/ref=wl_it_dp_o_pd_nS_ttl?_encoding=UTF8&colid=39XOLRFXN38YS&coliid=IF9R83I1CJ8HL).
May be you could let me know what you think after reading it?
Comment #147 August 31st, 2017 at 8:59 am
Scott #137
I have to agree with you too with what you describe both about the existence of the second quality and its correlation with moral goodness. It is not only important for success in science, but in life in general because no matter how well you start your life, the world is a very dynamic entity. So if you are unable to understand that the world changes, adapt to those changes, and stop judging people in absolute terms but rather understand that each of us start our lives in different initial conditions, the world will eat you alive sooner rather later. Some of the saddest people I know are those who went to good high schools as teens, then to good schools for college, got a good job at good company X (such as say, IBM in the early 1980s) who thought that their success was going to last forever unchallenged. On the other hand, some of the happiest people that I know are those who started their lives in less that optimal conditions and understood that they going to a bad high school, not getting in their first choice college and not getting into their dream company was not a reflection of their personal worth but that their might be a myriad of reasons why things didn’t go their way -including that they did not work as hard as others who did- and that through hard work and openness they could bring change to their own lives. The second type of story is very common for example among very successful entrepreneurs.
In short: human beings are very complex creatures that cannot be reduced to simplistic black and white categories. Let alone thinking along the lines that these categories are genetically determined. Which age, I have come to understand this to be a good thing, because it opens the possibility for redemption, whereas in a world where everything is a genetically determined black and white category, the end result would not be pretty (it would be something like a Nazi or Communist nightmare).
Comment #148 August 31st, 2017 at 9:15 am
Arko Bose #146
I’ll pass. Not because I don’t deny the existence of those letters or because they might paint Heisenberg on a better life. Here is the thing. If I were to selectively consider certain things that Hitler did, including lifting the spirits of a nation -Germany-, that was into economic turmoil after WWI before he reached power, I could also make Hitler look good. In fact, no other than JFK fell for this “sanitized view of Hitler”, even after WWII was over.
I don’t think people understand how severe the problem of support to Nazi policies among Germans during WWII and beyond was. I encourage everybody to read about https://en.wikipedia.org/wiki/Denazification and how the policy was abandoned because it would have meant to having to get rid of the talents of large segments of the German and Austrian populations. For example “the denazification process was often completely disregarded by both the Soviets and the Western powers for German rocket scientists and other technical experts, who were taken out of Germany to work on projects in the victor’s own country or simply seized in order to prevent the other side from taking them”
What about these surveys,
” A majority in the years 1945–49 stated National Socialism to have been a good idea but badly applied.
In 1946, 6% of Germans said the Nuremberg trials had been unfair.
In 1946, 37% in the US occupation zone said about the Holocaust that “the extermination of the Jews and Poles and other non-Aryans was necessary for the security of Germans”.
In 1946, 1 in 3 in the US occupation zone said that Jews should not have the same rights as those belonging to the Aryan race.
In 1950, 1 in 3 said the Nuremberg trials had been unfair.
In 1952, 37% said Germany was better off without the Jews.
In 1952, 25% had a good opinion of Hitler.”
What about Vichy France,
“Because teachers had been strongly Nazified, the French began by removing three-quarters of all teachers from their jobs. However, finding that the schools could not be run without them, they were soon rehired, although subject to easy dismissal.”
I think that with the totality of what we know about both the workings of Nazi Germany, the support it enjoyed among large segments of the German population, and Heisenberg’s own actions in other settings, it is very hard for me to believe the fairy tale that Heisenberg was a fifth columnist. Certainly the review you posted is not convincing enough for me to change my mind. And BTW, this goes along the lines of what I was talking about earlier. Heisenberg is not a demigod. In fact, nobody is. One doesn’t understand his own weaknesses until one is tested. I wish I could I say I have always behaved in an ethical, irreproachable manner when I have been confronted with tough choices in life, but that is not the case. So get over it. Heisenberg was a brilliant physicist and nobody can take that away from him. As a human being though, his record was less than stellar.
Comment #149 August 31st, 2017 at 10:41 am
Norbert Blum has retracted- see the paper on arXiv and look at comments.
Here is hoping that something of interest comes out of the attempt.
Comment #150 August 31st, 2017 at 11:17 am
One more question related to Blum, and hopefully not as ignorant as the previous. Has there been any work bounding the size of a circuit that is almost-monotone, in the sense that for a size n problem we are allowed only f(n) not gates where f is some slow growing function. There appear to be two ways of asking this question, either where the not gates have to appear before any other logic or where they are allowed in the middle or end of our circuit. The first one seems to be uninteresting since the monotone problems we care about are highly symmetric so simply having access to the negations of a small part of the input can’t make a difference. Has anyone done work on the other version?
Comment #151 August 31st, 2017 at 12:46 pm
TPWG #148: Your link to history.stackexchange provides good information about Heisenberg’s role. The other links by both you and Arko Bose are more problematic, since they contain too much interpretation and only one sided information. Heisenberg himself never claimed that he actively sabotaged the atomic bomb project. Some existing documents (patent applications for atomic bomb technology) cast a dubious light on the role of von Weizsäcker. So basing the claim that Heisenberg actively sabotaged the atomic bomb project on von Weizsäcker’s testimony is a bad idea. Heisenberg’s own version is that he learned pretty soon that war time Germany would be unable to build an atomic bomb, so there was no moral dilemma.
My own opinion is along the lines of: Ye shall know them by their fruits. Do men gather grapes of thorns, or figs of thistles? If somebody is bad, it will show in his actions and in the consequences of those actions. I fail to see the bad consequences of Heisenberg’s actions. So my guess is that he was not bad. But this doesn’t mean that he was good either, since then I would like to see the positive outcomes of his actions. Later in post-war Germany, he became a political actor and achieved some positive outcomes.
Comment #152 August 31st, 2017 at 1:25 pm
One (partly) out of topic quick question for Scott. In view of his paper https://arxiv.org/abs/1011.3245, does BQP \subseteq BPP imply that polynomial hierarchy collapses? It seems that this is not the implication (it would have been pointed out if this was the case), but asking just to make sure. Thanks
Comment #153 August 31st, 2017 at 1:58 pm
pupmki #152: As it happens, my VERY NEXT POST is going to discuss all this in detail—do you have paranormal powers or something?
Very briefly, though: no, we don’t know that implication, and we even know an oracle relative to which it doesn’t hold (due to Fortnow and Rogers from 1998).
What we do know is that if ExactSampBPP = ExactSampBQP then PH collapses, where ExactSampBPP and ExactSampBQP are the classes of exact sampling problems solvable in polynomial time by classical and quantum computers respectively. I.e., in order to get this collapse, as far as we know today, you need to broaden the type of computational problems you care about from languages (the things BPP and BQP contain) to sampling problems.
Comment #154 August 31st, 2017 at 2:07 pm
Joshua #150: I believe there’s a result saying that every n-bit Boolean function is computable by a circuit with only log(n) NOT gates, all other gates AND and OR. But I don’t remember how badly the transformation blows up the number of AND and OR gates, and I also don’t remember what happens when you go below log(n) NOT gates. In any case, if we’re just counting number of NOT gates, it’s clear that we go off a cliff extremely early.
But then, as you say, we can restrict the NOT gates to (say) only be near the top of the circuit (restricting them to be near the bottom won’t buy us anything, because of de Morgan), leading to more questions that I don’t know or remember the answers to.
Since I’m sure someone reading this blog knows the subject better than me, does that person want to chime in?
Comment #155 August 31st, 2017 at 4:37 pm
My goodness, is there a way to magically make the comments of “problem with gatekeepers” hidden from view on my browser? At this point I’m willing to install any browser that will allow me to do it, for God’s sake, even Edge if it’s necessary!
Comment #156 August 31st, 2017 at 5:48 pm
Dani #155: If you really want to, you can type
jQuery('li > cite:contains("problem with gatekeeper")').parent().hide()
in the console to hide all of his/her comments.
Comment #157 September 1st, 2017 at 5:54 am
@gatekeeper #128: “the Western values of equality, love and justice do not come from Karl Marx but from the Judeo-Christian tradition.”
Not from the original Judeo-Christian tradition, mind you. See Can Atheists Appreciate Chesteron? on Slate Star Codex. I think the distinction is important.
Comment #158 September 1st, 2017 at 8:52 am
Scott #133: Thanks, I was unaware of that page.
I agree that there are going to be way too many papers by cranks or others who do not appreciate how difficult a problem P vs NP actually is.
However, are there no proof attempts that are done with a full understanding of what they are trying to accomplish? Or at the very least are there no attempts that were done by people who knew everything there was to know at the time?
I have a general idea of why p vs np is hard partially from my CS education, but mostly from reading your blog and trying to make my way through the zoo as well as the Algebrization paper.
I guess what I was imagining was a place that you could send people to try and education them on p vs np with a small as possible barrier to entry. Instead of telling them to read half a dozen research papers, maybe a paragraph about why algebrization is a problem.
I mean I get why it would be fun to put up a webpage that mocks p vs np proof attempts (and it might even be the most effective thing you can do), but I just feel that if it does work it will be working for the wrong reasons.
Comment #159 September 1st, 2017 at 11:05 am
Harry Johnson #157,
Again, I understand that among the liberal intelligentsia Slate Star Codex is some sort of Oracle people use to understand that other side that these smart people profoundly believe to be misguided. But he is not a theologian nor he seems to know much about early Christianity.
He is probably unfamiliar with https://en.wikipedia.org/wiki/Didache , a 1st Century AD treaty with one of the earliest accounts of how the early Christians understood their faith. Pay attention to “The Two Ways”. I mention this, because the epistles of Paul, particularly the two to the Corinthians, are also pretty clear, but the Didache is a non biblical testimony that cannot be accused of being “the bible”. It’s an early manifestation of “applied Christianity” as understood by Christ’s earliest followers.
You are confusing Christ’s teachings with how his followers carried out those teachings. And that’s always a big mistake. Neither GK Chesterton nor CS Lewis founded the Christian faith. Christ did. All these two did was to explain it in terms the atheistic intelligentsia could understand. But then again, hundreds of millions of people had applied Christ’s teachings to their own lives throughout centuries without needing “intellectual” translators. Perhaps what this means, more than anything, is that like any other form of arrogance, that of the intellect also makes people blind to messages these smart people dislike.
Comment #160 September 1st, 2017 at 11:35 am
Scott #7.
On GR=QM. What are your thoughts on the below Arxiv submission, by Prof Leonard.
https://arxiv.org/abs/1708.03040
Comment #161 September 1st, 2017 at 1:56 pm
Scott #154 and Joshua Zelinsky #150
The construction with log(n) not gates that I’m aware of is that you start with a circuit of size n log^2(n) or something and get new variables equal to the negation of the binary expansion of the number of the original n bits that are true. So all the negations are relatively early in the circuit, and in fact the part of the circuit containing the negations can be fixed.
However, while it’s easy to see that an arbitrary Boolean function can be made monotone if you add these extra bits, this doesn’t work on the level of circuits, so you’re forced to use a trivial upper bound on the circuit complexity of an arbitrary Boolean function.
However, this is all based on the method to do the log(n) trick that I know.
Comment #162 September 1st, 2017 at 6:06 pm
@gatekeeper #159, in the context of speculation on Christianity’s historical influence on Western values, it seems obvious that the way that Christ’s followers have historically interpreted his teachings is far more relevant than your modern-day interpretation. Also, while I was interested to learn of the Didache, it is not obvious from the Wikipedia article that it is particularly consonant with modern Western values, nor that it was particularly influential on them.
There seems little point in further debate. I probably shouldn’t have brought this up in the first place, I don’t imagine Scott is at all interested; I’ll attempt to refrain from further comment.
Comment #163 September 2nd, 2017 at 4:43 am
DLI #158: So are you asking for something like—oh, I dunno—my 120-page monster P vs. NP survey that I spent a year writing, the one that tries to make accessible just about everything currently known about the problem, and all the major approaches that have been tried and where they hit obstacles? 😉
Comment #164 September 2nd, 2017 at 4:57 am
Mrityunjoy #160: As I said in the comments of my last post, I don’t think it’s in any sense literally true that QM and GR are the same theory.
I think slogans like that of Lenny’s need to be understood metaphorically, in which case they often contain profound insights. E.g., in the case of ER=EPR, I don’t think every entangled quantum state should literally be understood as forming a wormhole. On the other hand, the other direction seems to be solid—e.g., wormholes in an AdS bulk really do correspond to EPR-like entanglement on the CFT boundary, with the non-traversibility of the wormhole corresponding to the impossibility of using entanglement for superluminal signalling. And that was a major realization that was worth calling attention to.
In the present case, I don’t yet understand well enough what Lenny even means by “GR=QM” to try to translate that into a statement I’d agree with.
However, if you read the paper/letter in question, it talks a lot about building a quantum computer with qubits arranged in a spherical shell, in such a way as to simulate a CFT that has a bulk dual. And, through a variety of thought experiments, it ponders the question of whether such a simulation would literally bring the spacetime bulk into existence—i.e., whether there’s even a principled distinction between the simulation and the reality.
Personally, I’d respond that that’s indeed a profound question one can ask, but it can also be asked (and has been asked) much more broadly than in the context of AdS/CFT. E.g., wasn’t it the subject of those Matrix movies? 😀 More seriously, one could ask: why should it matter if the qubits of our quantum computer are literally arranged in a spherical shell? Why couldn’t they be arranged some other way, and still give rise to the bulk spacetime? But then we’re well onto the slippery slope with Nick Bostrom and the simulation hypothesis waiting for us at the bottom…
Comment #165 September 2nd, 2017 at 5:01 am
#159: So to the left, Scott Alexander is a closet alt-rightist / red-piller / MRA / insert-your-favorite-epithet, while to the right, his blog is just something that the “liberal intelligentsia” read? He really gets it coming and going, doesn’t he? 🙂
Comment #166 September 2nd, 2017 at 5:03 am
Will #161: OK, thanks!
Comment #167 September 2nd, 2017 at 1:09 pm
Scott #165
What I mean to say is that many of the things he says are common knowledge among those of us who grew up in a Christian home and in a Christian environment. As it happens, it wasn’t until I went to college that I met people who had been brought up by, for lack of a better word, the liberal atheistic intelligentsia. This is different from being just “leftist” on either the economic or social sense. I knew Christian leftists. At first I found these atheistic views fascinating and I tried to make it my own. I even joined a secular humanism club, believe it or not. Over time, I found it bankrupt as a “worldview”. It’s just liberal Christianity without references to God removed.
So what Scott Alexander says about Christianity in that post is just well known among people who are serious Christians. We never understood Christianity in any other way. Christianity teaches that salvation is by grace through faith in Christ as the Messiah promised by the Jewish scripture and that while the Law, which happens to be the same as the Jewish Law -ie, the tend commandments-, is necessary to lead a peaceful co-existence, nobody is justified by the Law. Live by the Law, die by the Law.
Harry Johnson #162. The Didache is just an example of an early testimony of how Christ’s earliest followers understood their faith. It speaks of the “two ways”, where one way was the way of the brutal Roman Empire, and the “the other way” was the Christian way which happens to be what we generally call “Western values”. And the Christian way is synonymous to Judeo-Christian (at least what Judaism taught until the first century AD) because Christianity is a strict super set of those teachings. Islam is not a super-set of Christianity, but rather a reformulation. Anyhow, there is plenty of literature on this topic and I encourage you to read what Jurgen Habermas had to say about it: “this legacy -the Judeo Christian legacy-, substantially unchanged, has been the object of a continual critical reappropriation and reinterpretation. Up to this very day there is no alternative to it. And in light of the current challenges of a post-national constellation, we must draw sustenance now, as in the past, from this substance. Everything else is idle postmodern talk”
Comment #168 September 2nd, 2017 at 3:21 pm
One more thing.
Scott, Harry Johnson. and the rest. If you want to know the person I usually look at for inspiration as both a great scientist as well as a great Christian, it’s John Lennox,
http://www.johnlennox.org/
If the name sounds familiar is because he held several high profile debates with Richard Dawkins at the peak of the New Atheism movement in the late 2000s and most observers found him -John Lennox- to be the most persuasive of the two.
Comment #169 September 2nd, 2017 at 4:48 pm
#168: I confess that I hadn’t heard of him until just now. Steven Weinberg has a great line somewhere, about how most scientists “don’t even think about religion enough to qualify as atheists.” I would add that, in my experience, that’s probably true even for most scientists who go to church or synagogue, celebrate religious holidays, etc. I admire Richard Dawkins for many, many things—his prose style, his intellectual courage, his ability to make vivid the logic of natural selection—but the argument against religion, to which he’s devoted so much of his life, just somehow hasn’t been much of a live issue for me since I was a teenager.
Maybe the best way to explain it is that, if someone offered to clear up any six of the following seven mysteries for me:
(1) the explanation for the low entropy at the Big Bang,
(2) a proof of P≠NP (or P=NP),
(3) the smallest k such that the value of the kth Busy Beaver number is independent of set theory,
(4) whether or not there’s intelligent life elsewhere in the universe,
(5) why the fine structure constant is about 1/137,
(6) whether the Schrödinger equation holds exactly at arbitrarily large scales,
(7) whether or not God exists,
my picks would be (1)-(6).
Comment #170 September 2nd, 2017 at 5:04 pm
Scott #169
Those are mysteries and I am afraid many of them, particularly (7), might remain mysteries for a long time if one restrict oneself to purely empirical and scientific arguments. I for one, when I went back from atheism to Christianity, did a lot of studying about the life of Jesus Christ and how his teachings essentially gave rise to Western Civilization. I found a lot of what I read very persuasive on its own terms, outside the biblical account. I stumbled into John Lennox while doing this research. Other people have different views.
What I can give you though, is a pointer to a talk that John Lennox offered to EPFL students 2 years ago which is one of his best on his arguments about science and religion. I imagine because the audience were mostly engineering students, he didn’t have to lower the tone to make it understandable to people of a different background:
Comment #171 September 3rd, 2017 at 7:47 am
Scott #164 : Isn’t sphere already used as the visualization for entangled qubits. Does it mean, that we can look for alternatives to unitary transformations? corresponding to bulk. Even though we may not literally put qubits on a sphere.
Comment #172 September 3rd, 2017 at 6:06 pm
Regarding two of the seven mysteries (nice list, btw)
(1) hep-th/0611088 suggests that it’s because the universe began as a torus in Kazdan-Warner class Z
(5) arxiv:1005.3033 suggests it’s because the extra dimensions of our F-theory braneworld consist of 24 or 25 fuzzy points
Comment #173 September 3rd, 2017 at 9:16 pm
Mitchell #172: Not having studied the papers, those sound on their face like explanations to which I’d actually just prefer “God did it.” 😉
Comment #174 September 4th, 2017 at 5:10 am
A few things:
1. If you’re going to commission a web app to communicate via microtubules with uncooperative oracles to determine whether a given P != NP paper holds up, it’s not surprising at all that Adam would be the guy to do the job. 🙂
2. wrt TPWG’s “timid outsider” objection to haspvsnpbeensolvedyet.com, a data point: I’m an (I’d like to think somewhat informed) outsider to the complexity community (there aren’t really any complexity theorists in Australia and I’m kinda tied down here for now) and if I had a good hunch on how to attack a big separation like P vs NP (or NC vs PSPACE, or…) I don’t see why haspvsnpbeensolvedyet.com would deter me from devoting a lot of time to it. The website just seems to distill community sentiment on barriers to established techniques down into one light-hearted web form — and I think anyone mathematically literate and careful enough to understand the question and known results should probably agree that things like relativization and RR are major barriers, whether they have a full-time post at a top-20 CS university or not. In fact, that consensus is valuable information for an amateur, and it’s backed up by detailed open-access articles written by passionate “institution” academics like Scott, which attempt to present the gory details in the most accessible possible light. So I really don’t see what the problem is, or how academics could do better by outsiders without spending far too much time patiently interfacing with cranks who don’t vet their arguments carefully enough and don’t bother to gain a coherent understanding of the barriers. (Both activities which help to make you better at the kind of mathematics you’ll need, by-the-by.) You should even feel grateful that researchers center and disseminate the study of the barriers, rather than sitting on negative results like some other research areas do!
3. I do, however, think that researchers should be less…sour?, about purported P != NP proofs, especially when it’s a fairly reputable researcher going up against high, rock-solid walls like RR. The physics teachers that Scott mentioned, who stand just beyond the highest point of a pendulum’s arc to demonstrate their faith in conservation of potential energy, aren’t just doing so because they believe they won’t get hit and die — they’re doing so because by *demonstrating* their faith in the fact that they won’t get hit and die, they inspire a sense of awe in the conservation of PE in onlookers.
I think the Blum paper could’ve been a bit more of a teachable moment. Not that there weren’t a number of theorists dissecting the paper, explaining barriers, etc — there certainly were, the likes of vloodin, Luca Trevison, Lipton, et al provided great insights — but the dismissive, “go home” attitude of some (including Scott) seems to waste an opportunity. And I realize that this opportunity comes with having to read/explain a lot of really hard and nitty-gritty legitimate lattice stuff that’s currently kicking my arse, and it tends to draw the cranks out like nothing else, so I don’t fault Scott for passing on this one until the paper was pretty clearly debunked. But it also gets more eyes on the monotone circuit bounds of Razborov and Tardos and others, and puts publicity (unfortunately at Blum’s expense) on a legitimate attempt at P != NP falling at the feet of Razborov-Rudich, which exhibits the power of the barrier and gets people interested in learning about it. It certainly got me to get off my lazy butt and finally properly learn about circuit bounds, I’m even planning on giving a talk about it at some point.
Failed P != NP proofs might be tedious to researchers in the community, but I don’t know, I think that when reasonably legit attempts surface in public they can be a net benefit to the field.
Comment #175 September 4th, 2017 at 5:29 am
Greg #174: Thanks for the comment. I agree with you that these P≠NP claims can be teaching and learning opportunities, and I also agree that what vloodin and the others did—i.e., actually delving into the proof to figure out the problems—was higher-value than what I did.
But one aspect of these episodes that doesn’t get enough attention is immediacy. If I’m sent a paper to referee, then even in the most crunched, last-minute situation, and even with the stakes being 0.0001% of what they are with P vs. NP, at the very least I’m given 2 or 3 weeks to read the thing and send comments—in recognition of the fact that the editor has no idea what else might be going on in my life at that moment, and actually reading a technical paper is hard and takes large, contiguous chunks of time.
By contrast, when journalists, or just random people on the Internet, contact me about a P≠NP claim—or for that matter, a D-Wave speedup claim or whatever else—they want an answer now. In such cases, I might even have an answer that I’m 99.99% confident about, but I won’t have a justification for the answer that would convince a determined skeptic.
So then, what do I do? Do I drop everything else (including travel and family obligations) to find that justification ASAP? Do I say “who knows? impossible to guess…,” and then pretend to be surprised when the answer turns out to be exactly the one I expected with 99.99% confidence? Or do I share my Bayesian estimate, and risk getting egg all over my face if I’m wrong, and people calling me “arrogant” even in the vastly more likely case that I’m right? 🙂 What would you do?
Comment #176 September 4th, 2017 at 7:50 am
Scott #175: yeah, I’ve done a tiny bit of journal review. It’s kinda shocking to, having marked hundreds of students’ flawed algorithms assignments, then go on to review the work of established academics and discover that the standard of work pre-review is sometimes not all that much higher. Even when the standard is high, I agree it’s grueling work that takes a lot of time. (Though even still, typically not as much time as a paper that trawls through descriptive complexity or monotone circuit bounds research.)
I haven’t, on the other hand, ever had to interact with press. I don’t envy your situation; I certainly don’t have an answer you’re not likely to’ve heard before. Maybe you just need to ease up on the scruples a little more and accept that people are going to label you “arrogant” for tapping the “P != NP proof attempts are unlikely to hold up due to tremendous well-known barriers” sign? Based on the number of responses to TPWG you’ve written I’m not too optimistic about this being actionable advice for you. Or, you could just let the email event horizon take care of it for you.
Maybe in the far-flung future we’ll have figured out how to present the barriers as pop science and journalists will be able to inspire as much awe in RR thwarting complexity theorists’ best-laid plans as they do in explaining how you can solve TSP by initializing a quantum register to a uniform superposition of every admissible round trip, then applying a classical verifier, then getting a goat and a dagger, then… (okay, maybe I’m hoping for far too much from popsci)
But it occurs to me that none of this really addresses the real issue, which is that you’re being attacked by a swarm of gnats. So when you hastily write a note on a blog article saying “go away”, you mean “go away gnats”, and other like myself read it as “go away everyone”, and it seems like you’re closer in opinion to the kind of person who got into a huff about Terry Tao wasting entire hours of precious, limited genius brainpower on the Deolalikar proof attempt than you actually are. So my point 3 above misinterprets you, which I apologize for.
As for the gnats, maybe Adam Chalmers can help you? He seems to suffer from recurring incidents involving being attacked by swarms of bees, which I’m not sure I understand, but it seems terrifying and like something he has probably had to solve to, like, not die. Are you still hanging around here, Adam?
Comment #177 September 11th, 2017 at 10:14 pm
I find the discussion of communism vs Nazism fascinating. In a group of incredibly well read people (it probably took me several days to find the time to do follow up reading), it seems to me people are taking only 3 examples of communism as the only measure of it.
That seems broadly ignorant of the bigger history of socialism. Looking back at the last 125 years of societal development, it wasn’t Christian groups that led the charge, but socialists inspired by Marx that brought us national pension systems, universal medical care, a welfare state to significantly combat homelessness and hunger, the labor movement to protect workers rights, etc, etc, etc. In fact, much of what we deem “progress” socially can find it’s roots in Das Kapital. It should be a stunning example that within 50 years of Marx these systems started to come about from ground swell efforts and most would agree these were all for the better.
So if you want to talk about the relative merits vs Nazism, the best way to measure it is to see how much of the core ideas of each are still alive and well across all of Western society. Communism has examples so numerous it is hard to list while Nazism has none to my knowledge. In my mind that in itself creates an obvious gap in the value of the two world views.
Comment #178 September 12th, 2017 at 3:16 am
Sean #177:
In fact, much of what we deem “progress” socially can find it’s roots in Das Kapital. It should be a stunning example that within 50 years of Marx these systems started to come about from ground swell efforts
That seems to me like a textbook post hoc ergo propter hoc.
Social reform and workers’ rights movements were already developing and starting to have successes before Marx came on the scene, and they continued to gather steam independently of Marx. And orthodox Marxists opposed those efforts, seeing them as mere palliatives that would delay the true proletarian uprising, and the reformers’ commitment to nonviolence and democratic norms as hopelessly naïve and outdated. So I don’t see that Marxism gets to take any credit for improvements in working conditions, medical care, etc. that happened not only separately from Marxism, but directly counter to Marx’s predictions. (Or if it does get a tiny bit of credit, I think the causality is indirect, as in: the threat of Marxist revolution might have caused those in power to be more open to liberal reforms, as reasonable and mild by comparison.)
Comment #179 September 13th, 2017 at 12:35 pm
Sean #177
To what Scott said, I will add that I find it astonishing that there is still people defending Marxism along these lines when we have the historical data we got from the Cold War. Consider what happened in Germany and the Korean peninsula. On both cases we are talking about exactly the same “people” from an ethnic, cultural and historical background. The capitalist halves on both cases thrived whereas the Communist ones became miserable. We don’t know a lot about the internal workings of North Korea but we can definitely say that 40 years of Communism were so damaging for East Germany that 25 years into German reunification, the differences caused by 40 years of Communism still ran deep https://www.theguardian.com/world/2015/oct/02/german-reunification-25-years-on-how-different-are-east-and-west-really .
Cultural Marxism must be one of the most corrosive -intellectually and spiritually- ideas ever invented by humans. Jordan Peterson explains here how it now takes the form of post-modern thought: https://www.youtube.com/watch?v=wLoG9zBvvLQ .
In the discussion Communism vs Nazism, my opinion is that both are so evil that getting into a discussion of which one is worse is pointless. Still, one of the things that has traditionally differentiated Communism from Nazism is that the former’s prescriptions have always taken the form of insidious, “good on the surface”, “who with a good heart would oppose them” policy proposals. It is not uncommon to hear, for example, very smart people praising Cuba for having “good preventive healthcare” for example as it happened to me recently.
CS Lewis already noticed something similar in his Screwtape Letters
“The greatest evil is not now done in those sordid “dens of crime” that Dickens loved to paint. It is not done even in concentration camps and labour camps. In those we see its final result. But it is conceived and ordered (moved, seconded, carried, and minuted) in clean, carpeted, warmed and well-lighted offices, by quiet men with white collars and cut fingernails and smooth-shaven cheeks who do not need to raise their voices. Hence, naturally enough, my symbol for Hell is something like the bureaucracy of a police state or the office of a thoroughly nasty business concern.”
Every Communist society ever attempted ends up with a police state causing evil of apocalyptic proportions through the coercive force of government.
Please, don’t fall for the scam that one for of totalitarian society is better than another form of totalitarian society. Human beings are inherently crooked. It is not policy prescriptions that deliver evilness, but humans endowed with limitless power that do -check http://avalon.law.yale.edu/18th_century/fed10.asp – , regardless of the underlying ideology. Both Communism and Nazism are totalitarian and both believe that collateral damage is acceptable to achieve the desired goals.
Comment #180 September 15th, 2017 at 3:16 pm
#178/179:
I have to respectfully disagree with several points.
First, no labor movement that even resembles what we would call the modern movement predates Marx (I could be wrong but would need a substantial example, most I know of safe to the 1870s and 1880s).
Second, and most important, you are setting an impossible standard, saying you aren’t a true Marxist or socialist or communist unless you engage in a particular way. That is, from my perspective, a bit excessive and paternalistic. The leaders of the modern labor movement and social safety net movements saw themselves as avowed communists or marxists broadly speaking (and is also why they were accused of being unamerican and communist by political and business leaders).
If those people join a communist political party and call themselves communists, who are you to argue now they weren’t real communists (I am avoiding the term Marxist because that wasn’t the common self identification in the late 19th and early 20th century).
Let me give an example, I could claim that everyone who calls themselves a Christian is wrong is they don’t follow a particularly strict form enshrined in laws in some African countries (death penalty for homosexuality, etc) and they are fakers simply because they don’t push for those laws. I can even point to text in the Bible that says those laws should exist to bolster my point. But you wouldn’t then make the argument these people spent their entire life not living by the rest of the ideas in the Bible. It’s the same here. The decision to not engage in excessive outright violence does not mean the rest of their efforts weren’t informed and inspired by the ideas put forward by Marx (and others in less coherent form before him).
Second, TPWG, your making a false equivalence. I never argued about the relative qualities of full totalitarian communist (as in Stalin, Mao, Lenin and Kim) vs some pure form of liberal democracy. I argued that several ideas that originated or were made broadly popular by communists and communist ideals are enshrined in our life in the west. If you feel differently. Pointing to NK or East Germany isn’t the answer. You’d have to point out that the leaders of the labor movement and social welfare pushes weren’t either avowed communists or known to have strong communist leanings (something well documented so you’d have to make a substantial effort to overturn this accepted view).
of course, we could also use the example of India which was built broadly on socialist principals as a democracy to show a non-police state broadly inspired by communism.
Naziism has no such contribution to the public sphere. That’s all I need to see the difference, and why I’m not scared at all of a self identified socialist (on first principles, and I’m avoiding Marxist because we could get into an argument of if you can be one and want to work within democratic norms to pass laws) but am of a self identified Nazi.
Comment #181 September 16th, 2017 at 11:48 am
Sean #180
Not only your arguments are non convincing, they are a-historical.
Everybody who has been indoctrinated with the sanitized version of Communism/Marxism (pick your word, I am not getting into a pointless semantics argument) knows how the story goes: it is either that we have never known pure Marxism applied as Marx intended only bad implementations -thus there is hope for a utopian Marxist future where everybody will be happy- or that Marxism might have been bad, but it left us good things, like the ones you mention.
Here is the reality: humans who perceive to be oppressed getting organized in the fight for rights is as old as humanity itself:
– Here is a political movement in which “common people” fought for better representation and more rights https://en.wikipedia.org/wiki/Conflict_of_the_Orders . It happened in what later became the Roman Empire between 494 BC and 287 BC. Surprise, surprise. Or maybe not. After all, the Chinese Cultural Revolution, that sought to erase the past, is as Marxist as Marx itself. Why would a Marxist study ancient history?
– What about medieval guilds that feudalism encouraged http://www.lordsandladies.org/guilds-in-the-middle-ages.htm ? Similar concept. Further: the historical fact is that feudalism lasted for at least 1000 years (since the fall of Rome to the Renaissance), probably even longer if we make the cut-off with the enlightenment era and the American/French revolutions. It takes a lot naivete to believe that people put up with it if it weren’t because large portions of the population benefited from such a system.
What we call today “organized labor” was the reincarnation of these efforts that started during the Industrial Revolution around the second half of the XVIII-the century, well before Marx.
Marxists have never seen a good idea that they haven’t tried to hijack. This notion that they brought to the world the idea of people getting organized to fight for a common goal is another of the Marxist fantasies. What Marxism added is a way of doing this: infiltration and subversion of stable institutions. That’s why Marxists are so numerous in academia, for example. But a particular method, is not the same as a concept. As I said, Marxism is one of the worst ideas ever conceived by humans because it corrupts both spirit and INTELLECT.
Comment #182 September 25th, 2017 at 12:46 am
Scott, though my comment is not directly related to the OP, I wanna ask: if you or anyone currently working on quantum computing or the P vs NP problem made an ‘unexpected’ breakthrough (Alexander Fleming’s discovery of penicillin is a great example) and prove that P = NP, with a hands on and readily applicable solution to NP-Complete problems; would you recommend immediate publication of the thrilling findings to the community, despite its ‘devastating’ consequences for cryptographic schemes such as RSA? Or would you instead warn that an alternative should be used, such as Information Theory (I can’t tell how difficult–or easy–such a transition from RSA to Information Theory would be). What do you think???
(Pls don’t ignore… believe me this question is not out of place…)
Comment #183 September 25th, 2017 at 3:24 am
Data #182: If I actually proved P=NP, I hope that I’d follow the standard procedure in the computer security community for releasing results that break currently-deployed systems. Namely, first you announce the result (in the case of P=NP, it better be accompanied by a dramatic demonstration, like factoring giant numbers, proving the Riemann Hypothesis, etc., to make the world take seriously that you achieved something dramatic). Then you give everyone a grace period—maybe 3 months—to move to new forms of security. Then you release the details.
Before doing all that, I might not be averse to mining and then selling a few billion dollars’ worth of Bitcoin, or as much as I could before arousing everyone’s suspicions. Mostly for donating to worthy causes, of course. 🙂
Comment #184 November 1st, 2017 at 7:53 pm
[…] / Charlottesville / Blum / P vs. NP, I couldn’t help but ask him about whether my naive idea has any chance of proving ALogTime != PH, even if just for testing whether he really keeps such an open mind. His answer was: “I […]
Comment #185 May 5th, 2018 at 10:52 pm
I know I’m late to comment, but I’ve been thinking for a bit on your website, http://haspvsnpbeensolved.com, and the fact your code is closed source is concerning to me. At the very least, what are your priors?
Keep in mind, we’d expect any correct proof of P vs NP to utilize new techniques or a paradigm shift. If, for example, a proof correctly finds a logical inconsistency with ZFC, whatever it may be, then it is very likely to disagree with known theorems, which would disagree with your priors and your algorithm will produce a false negative.
Comment #186 May 6th, 2018 at 3:38 am
Mark #185: It’s not actually closed source. Try clicking the lower right-hand corner.
Comment #187 May 6th, 2018 at 11:13 am
Well, that makes a big difference! I was taking this seriously… I assumed you had a PDF to text converter which allowed a machine to pick up on cues based on a previous post of yours: https://scottaaronson-production.mystagingwebsite.com/?p=458
I wouldn’t bother you to read my paper PvsNP paper, but I do source and address your work with Yedidia on BB7918. This paper of yours gave me a huge startle and made me think I was wrong for quite some time, until I realized something about an implied axiom in use on certain proofs by contradiction. I almost had to retract! But a revision sufficed.