I was going to write a post about how hard it was to find what grades mean at different schools (e.g., at UMCP W (for withdraw) means the student dropped the course, but at UT Austin its Q (for Quit?)) but then I found that my Googling
Name of school grade key
I could find it. Okay, so grade keys are not that hard to find.
WEB BAD:
However, course descriptions are. Both questions (what grades mean and course desc) came up when I do admissions for my REU program. If a student has a course in Discrete Mathematics that could mean a course where you learn how to prove simple things OR it could mean a course where you proof the graph minor theorem (actually I doubt that) or something in between. Similar for Principles of Programming languages and Software Engineering in that they could mean a variety of things. I think math and physics are more standardized, but even there you have the problem that Advanced calc could be either multivar or a course with proofs or something else. There is a great related XKCD here.
PEOPLE USING THE WEB BADLY:
Fellow blogger Scott Aaronson recently posted about Vivek Wadhwa's Washington post column on quantum computing (the post is here) The article by Vivek told the tired and utterly false story that QC can be used to solve TSP by looking at all possibilities. Should Vivik have known better by looking at the web? At first I thought YES he should know better. But then I thought -- I should try to see what he might have done. Maybe the web has this one wrong. In fact, some of my students Iwho, I should add, are not writing articles on QC for the Washington Post) tell me that they don't need to learn the proof of the Cook-Levin theorem since Quantum Computers can solve SAT anyway. So I decided to pretend I didn't know anything about QC and went to the web to see what I could find. First stop: Wikipedia. I found the following quote in the QC article:
BQP is suspected to be disjoint from NP-complete and a strict superset of P though this is not known.
So, the first place I look I find that BQP is suspected to NOT solve SAT or TSP or... Realize that Wikipedia is not some obscure source of hidden knowledge. It is literally the first place one would look. Hence, no excuse, even if other experts told him otherwise (which seems to be the case, though `experts' should be in quotes) the Wikipedia quote should at least give pause.
So even when Wikipedia gives the right information, not everyone looks there.
"BQP is suspected to be disjoint from NP-complete and a strict superset of P though this is not known."
ReplyDeleteThis 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 ;).
Full paragraph:
ReplyDelete"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." (source)
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.)
On a side note, a few days back I came across the following sentence at the start of a nature scientific report (link):
"Prime factorization is at the heart of secure data transmission because it is widely believed to be NP-complete."
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.
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.
ReplyDeleteBill, have you asked your students who think that QC can solve SAT (quickly) why they think that?
ReplyDeleteThere is plenty of (technical) stuff on wikipedia that is just plain wrong...
ReplyDelete