tag:blogger.com,1999:blog-3722233.post3262168094346690140..comments2024-09-15T21:31:40.175-05:00Comments on Computational Complexity: Good article, terrible headlineLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-69842964482174393972019-04-23T08:17:57.285-05:002019-04-23T08:17:57.285-05:00I don't think it is that hard to explain the s...I don't think it is that hard to explain the significance of an oracle such that BQP is not in PH. I could explain it to my friends in undergrad algorithms class. <br /><br />One can think about NP as exists-P, and if you generalize this to arbitrary sequences of quantifiers you get PH. Just as we believe NP (exists-P) is different from coNP (forall-P), we believe that PH doesn't collapse.<br /><br />Now, the natural question is where does BQP go? (On a sidenote, we know that BPP is in PH. One implication of this is that if P=NP, then P=BPP or randomness doesn't give an "edge.") If P=NP, does it also imply that BQP=P (quantumness doesn't provide an edge)? An easier question is, is BQP in PH? Another perspective is, one can think about PH in terms of bounded games, can we think about BQP as a game? We think the answer is NO. But since we cannot even prove that P ≠ PSPACE, we cannot prove that BQP is not in PH. The best we can hope for right now is a relativized world where this holds. Recall that if this does hold, then it holds in at least one relativised world.Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81368625392184281072019-04-16T12:21:16.296-05:002019-04-16T12:21:16.296-05:00Now you know what Trump's been talking about. ...Now you know what Trump's been talking about. Media = Fake news. They like exaggerating things just to increase their readership.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86803565361770845792019-04-15T19:58:03.346-05:002019-04-15T19:58:03.346-05:00AH- that could explain why the article (which ment...AH- that could explain why the article (which mentioned my poll) is actually okay, but the headline is not.<br /><br />As for Turing's Oracle and the Quantum paper--- article and headline both terrible.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64229873231652738092019-04-15T19:51:23.068-05:002019-04-15T19:51:23.068-05:00The headline makes perfect sense from THEIR perspe...The headline makes perfect sense from THEIR perspective. It gets you to pay for the article and then you find out the truth. It is a teaser to get you interested.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29345313717962376652019-04-15T14:36:51.796-05:002019-04-15T14:36:51.796-05:00This would be a good to bring up with the math and...This would be a good to bring up with the math and science journalists like @evelynjlamb and @CaraSantaMaria. <br /><br />Also, isn't New Science notorious for getting things wrong? Or am I just passing along insidious gossip?Mitchhttps://www.blogger.com/profile/06352106235527027461noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22504379487269641402019-04-15T12:05:59.160-05:002019-04-15T12:05:59.160-05:00It's probably not the writer's fault, as h...It's probably not the writer's fault, as headlines are the exclusive responsibility of editors. I learned the hard way that even when I write opinion pieces, I have very limited control over their headlines. Anonymoushttps://www.blogger.com/profile/10820493705070900372noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79697077970105225872019-04-15T08:44:29.229-05:002019-04-15T08:44:29.229-05:00It not just TCS, but science in general. See for ...It not just TCS, but science in general. See for example this amazing <a href="https://twitter.com/justsaysinmice" rel="nofollow">twitter feed</a>.uncudhhttps://www.blogger.com/profile/05130336421294974004noreply@blogger.com