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.