Michael Goldweber writes: “[M]y embarrassment-free non-majors course will contain units on both complexity as well as unsolvability. … One might argue that an educated population that understands the limits of what can be accomplished with computation is more important than an educated population that has spent a semester wresting with a compiler or creating games in Scratch.”

While I share his view that computability and complexity are fundamental concepts that should be studied, I believe that focusing on them is highly misleading as to what actually goes on in computer science. You can teach students that SAT is NP-complete, however, they will miss out on the more important information that SAT solving has become one of the most successful problem-solving methods in computing! SAT solvers implement very clever algorithms (with scary names like “conflict-directed clause learning with nonchronological backtracking”) and data structures (“watched literals”) that make the NP-completeness of SAT irrelevant in practice. The field is so rich that the “Handbook of Satisfiability” is almost a thousand pages long.

It may not be practical to teach modern SAT solving to non-majors, but I don’t think that a teaching an esoteric theoretical result in isolation is critically important for an educated population. Suppose that a software engineer comes to her boss who learned (only) about NP-completeness and proposed to use a SAT solver in the company’s core business. The boss would chase her out of his office for suggesting such nonsense. It is just conceivable that if the boss had spent a semester “wrestling with a compiler,” he might be more receptive to the idea that sophisticated software systems have immense potential for solving problems.

I wrote something relevant in a CACM Viewpoint (Non-myths about programming. CACM 54(7), 2011, 35-37), where I tried to show (with apologies to Winston Churchill) that computing is the worst profession, except for all the rest.

I just ran across an article that seems to support your feeling: http://www.insidehighered.com/news/2013/02/01/connecticut-and-texas-aim-grow-stem-enrollment-take-different-approaches It talks about increasing undergraduate participation in STEM, but when you look at the details it’s all about increasing engineering enrollments. I wanted to share.