Bill G. had an interesting post recently (see also here) touching on the question of whether or not to teach Mahaney’s theorem in a course on complexity theory. (For the record, I did teach Mahaney’s theorem when I last taught complexity theory, but I would probably omit in the future.)

To me the more interesting question at the core of this issue is *what is the goal of the courses we teach?* Clearly it is not possible to cover everything, and so choices must be made; if we can determine the goal of the course we are teaching, it should become easier to decide what stays and what goes. Of course, the goal of a course depends on the instructor, the course, the audience, and possibly more. But can we classify the *range* of possible goals of a course, in general? Here’s what I was able to come up with; I’m happy to hear more suggestions (note that while my examples are CS-specific, I’d like to think that these cover any course, at any level, in any area):

*Pure intellectual interest*. I imagine many courses in the humanities would fall into this category, but there is no reason this could not apply to courses in any discipline. One could also probably make the case that courses at the advanced graduate level fall predominantly into this category.

If this is the goal of a particular course offering, then it’s really entirely up to the instructor what to cover. Presumably, though, the professor would try to select material that many of the students would find appealing, rather than only selecting material that the professor found interesting.*Practical application*. At the other extreme, some courses are taught with the specific goal of conveying a particular skill. In computer science, that would obviously include a course on Java programming. But even higher-level courses can fit here: for example, in a graduate course on Algorithms there may be students who might actually apply some of these ideas in their jobs after graduate school.If this is the goal, then the professor’s job is to try to match what is taught to what will actually be useful in the real world. This by no means implies that only concrete tools (e.g., specific algorithms, to continue the example from above) can be taught;

*techniques*and*ideas*that often seem to arise in practice are also fine.I will include in this category courses that are taught primarily as prerequisites for some other course(s); in that case, the “application” is simply the subsequent course(s).

*General exposure*. The goal here is to teach “what any person taking such-and-such a course should know”. This is a bit vague, so how about some examples: Michael M. recently posted about “core” topics every theoretical computer scientist should know; a grad student interested in TCS might want to take courses (or perhaps one dedicated course) whose goal (at least in part) was explicitly to cover this material. At the undergraduate level, there are constant debates about “what someone with an undergraduate CS degree should know” and so, again, there must somewhere along the way be courses whose goal is general exposure to such material.The professor’s job here is to keep the material relevant, in part by keeping in sync with what people are teaching elsewhere.

*Research*. This makes sense primarily at the graduate level, though a course at the undergraduate level serving as a prerequisite for a graduate course could also be said to fall into this category. Here, the course is intended for students with an interest in doing research in some area, and the professor’s goal is to teach the most up-to-date material, possibly with the most relevance to current research trends.

Making things more difficult is that courses often have multiple (possibly conflicting!) goals: for example, in an Intro to computer science course you need students to learn the mechanics of programming yet you also hope to convey some of the excitement of the field, all while balancing the need to cover the appropriate prerequisites for later courses. In a graduate course there are likely to be some students whose intention is to do research in that area — and whom you’d like to attract as graduate students — but there are probably many more graduate students taking the class to fulfill a general requirement and for whom one of the other goals might be more appropriate. I find these issues always arise when I teach; unfortunately, it seems it is impossible to satisfy all the students, with the end result being that all the students end up dissatisfied. As I teach computer security this semester, deciding what the goal of the class should be is something I still haven’t fully resolved, but that is the topic of a future post…

**An aside:** Coming back to the question of teaching Mahaney’s theorem, I did not see any compelling reason in the comments to Bill’s post as to why it should be taught. I’m no expert, but to me (1) it does not seem related to current research topics; (2) it does not seem inherently interesting (unless one ties it into the Berman-Hartmanis isomorphism conjecture; even then, it’s not clear to me what is lost by covering the BH conjecture but omitting Mahaney’s theorem); and (3) it does not seem to have applications to something else one would like to cover. One could make the case that Mahaney’s theorem is something “anyone taking a complexity course should know”, but as Sanjeev points out in a fascinating comment here, the perception of what someone “must know” is very generational.

## Leave a Reply