tag:blogger.com,1999:blog-3722233.post3843782443995752343..comments2022-11-30T08:54:37.970-06:00Comments on Computational Complexity: The web bad/People using it bad.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-91830085390341847712018-02-22T19:20:34.253-06:002018-02-22T19:20:34.253-06:00There is plenty of (technical) stuff on wikipedia ...There is plenty of (technical) stuff on wikipedia that is just plain wrong...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59685066023901157942018-02-21T18:45:22.063-06:002018-02-21T18:45:22.063-06:00Bill, have you asked your students who think that ...Bill, have you asked your students who think that QC can solve SAT (quickly) why they think that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9465959969393808592018-02-21T10:09:00.110-06:002018-02-21T10:09:00.110-06:00As someone in theory/mathematics, you have the adv...As someone in theory/mathematics, you have the advantage of knowing that Wikipedia is actually a trustworthy source for theory/mathematics information. This fact might be surprising to journalists, who (understandably) prefer to rely on quotable "experts". True "experts" should know that science journalism almost always amplifies hype (naturally, since this makes the story), and should guard against that. The "experts" seem like the main problem in this case.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5404909655299212702018-02-19T16:18:16.715-06:002018-02-19T16:18:16.715-06:00Full paragraph:
"BQP is suspected to be disjo...Full paragraph:<br /><em>"BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false."</em> (<a href="https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory" rel="nofollow">source</a>)<br /><br />Even most computer science undergrads I know struggle with NP, NP-Hard and NP-Complete. To them the fact that factoring is not in P but in NP immediately implies that it is NP-Complete. The accompanying figure doesn't help them that much either. I think Wadhwa got them mixed up too. (He doesn't mention "NP" in the article.)<br /><br />On a side note, a few days back I came across the following sentence at the start of a nature scientific report (<a href="http://rdcu.be/Hm5M" rel="nofollow">link</a>):<br /><em>"Prime factorization is at the heart of secure data transmission because it is widely believed to be NP-complete."</em><br />This is peer-reviewed research in quantum annealing! If peer-reviewed research can be that wrong, then extrapolating for popsci, the WP article is actually not that bad.Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31470870630533000782018-02-19T03:53:20.294-06:002018-02-19T03:53:20.294-06:00"BQP is suspected to be disjoint from NP-com..."BQP is suspected to be disjoint from NP-complete and a strict superset of P though this is not known."<br /><br />This sentence might be easy to find, but I'm not sure it is easy to understand for someone not used to complexity theory. Then again, two sentences later the Wikipedia article literally states: "There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false." That one seems clear enough to me ;).Thamashttps://www.blogger.com/profile/17766605868066955395noreply@blogger.com