CS172--Computability and Complexity explores the fundamental capabilities and limitations of computers. Students learn about problems that are unsolvable by any computer, no matter how fast or powerful; they learn about machines that analyze descriptions of other machines; they learn about infinities that are infinitely larger than other infinities. It is an area that can be intimidating and mysterious.

One principal technique used throughout the course is reduction--a method for showing that one problem can be solved in terms of another. Reductions are a critical aspect of computer science theory; many of the problem sets and tests in CS172 feature them in some way.

To construct a reduction from one problem to another, you need to have a deep comprehension of both problems as well as a solid knowledge of the framework in which to place them. Trying to have an understanding of all of this at once can be a bewildering experience. For this reason, many of my students initially had trouble tackling reductions.

I quickly realized that it was imprudent simply to hope that they would develop an intuition about reductions; it had taken me years to nurture my own intuition, after all, and I would be expecting my students to cultivate theirs in a matter of weeks!

So I formulated a method for my students that made solving reductions easier. It emphasized two appealing aspects of computer science: the precise, predictable way in which a computer operates, and the creativity involved in coercing such a simple machine to do complex, beautiful things.

My primary insight was that the reduction framework was itself precise and predictable, as the format of most mathematical proofs is. When teased apart from the creative aspect of the reduction, it was quite obviously mechanical in nature, and provided a wonderfully non-threatening platform from which to solve the rest of the problem.

Everyone knows how to order food at McDonald's, for instance; the only tricky part is deciding what to get. At a new eatery, however, you don't know whether to sit or wait to be seated, whether to pay at the beginning or after the meal--never mind what you actually want to eat! By eliminating the uncertainty of the process, I made every reduction a McDonald's reduction.

"Pretend you are a computer," I'd say, "and that you have been programmed to output the correct reduction between these two problems. The first step is to declare the implication you are about to prove...," And so on. About halfway through a reduction proof comes the moment of truth, the burst of creativity necessary to tie the two distinct problems together. It was here that I would implore the students to turn off their internal computers and instead capitalize on their natural ingenuity. Once that was done, they could switch back to computer mode to finish the proof.

The students took to this method with relish. Having worked with computers for several years, they were very comfortable simulating one; furthermore, the automated approach lent an air of familiarity to the process that made each reduction more palatable. Secondly, the clear demarcation between straightforward computation and thought actually accentuated my students' creativity: they were more successful about thinking freely when they knew they were supposed to.

I began to notice results immediately, including increased consistency and correctness on problem sets, fewer "how do I approach this?" questions in office hours, and more coherence during discussion section. Less objectively but more importantly, students reported greater comfort and confidence in dealing with reductions: the problems became challenges rather than burdens. Best of all, the essence of the reduction technique--knowing when to be a computer and when to switch back to being human--illustrated in a powerful way the strengths and weaknesses of computers, giving the students an intuitive, intimate perspective on the very nature of the course.