tag:blogger.com,1999:blog-3722233.post1823454938351268253..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Changing the ORDER you teach things in might help A LOTLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-55854508566194472712014-04-24T16:10:09.311-04:002014-04-24T16:10:09.311-04:00Sipser's book does 3-SAT <=_p CLIQUE before...Sipser's book does 3-SAT <=_p CLIQUE before Cook-Levin, on the reasoning that in order to understand the definition of NP-completeness you need a compelling example of a p-reduction. I agree with this.<br /><br />When I do computability in the middle third of the "Sipser" course, I am relying somewhat on the fact that our algorithms course is a prerequisite and so they are supposed to have seen NP-completeness to some extent. But our instructors for that course vary in the amount of time they spend on NP-completeness, as well as the level of similarity to computability in their presentation.<br /><br />I also try to spend a week on Turing machines in the discrete math course that comes before algorithms -- this is enough to give a somewhat hand-wavey proof of the unsolvability of the halting problem.DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18008518261518128562014-04-22T11:31:53.338-04:002014-04-22T11:31:53.338-04:00LOL … Ed Witten studied history and linguistics fi...LOL … Ed Witten studied <b><a href="http://en.wikipedia.org/wiki/Edward_Witten#Birth_and_education" rel="nofollow">history and linguistics first</a>,</b> <i>then</i> modern mathematics, and quantum physics <i>last</i>. <br /><br /><b>Question</b> Do texts like <i>The Feynman Lectures</i> introduce quantum mechanics far too early in the curriculum? Before students are adequately grounded in history and mathematics?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.com