Theorems and Proofs—which are more important?
Ken and I wish to thank all who read and follow us. May you have a wonderful day today all day.
But we would like to pose a basic question about teaching complexity theory: Theorems vs. Proofs.
Because today is in the US a national holiday I am not teaching my class on complexity theory, nor is Ken teaching his. I like the class, but I do enjoy the time off from lecturing. Still it seems like a time to reflect on a simple question about teaching.
Today is, of course in the US, Thanksgiving Day. We watch parades, really mainly the Macy’s Thanksgiving Day Parade; we watch football, that is NFL style football; and we watch our waist-lines expand as we eat too much wonderful food—my favorite is the turkey, covered in gravy and served with mashed potatoes.
So while you are enjoying your day let Ken and I ask you a simple question.
What we are interested in is this: Is it as important to know the statement of a theorem as it is to know the proof of the theorem?
I think we almost always when teaching follow the following paradigm:
- Define needed terms;
- State the theorem in question;
- Then present the proof of the theorem .
Thus our question is: Can we skip presenting the proof? Do students still learn something important if they know the statement only of a theorem, but do not learn the proof—or even an outline of a proof? I have wondered over the years of teaching, especially a course like complexity theory, whether we must give both theorem statements and proofs.
There are of course many situations in math where we know the but not the . Perhaps the most famous example is the classification of simple finite groups. This theorem gets used by theory papers but I believe that almost no one applying it knows the proof. You could argue that this is an extreme example, but there are many others that come to mind: the famous regularity theorem of Endre Szemerédi can be used I believe without knowing the proof. As an extreme example I have wondered whether it would be worth it to increase the material I present in class and do this by only proving a small subset of theorems.
I (Ken) am teaching our graduate theory of computation course. This course was until recently required of all PhD students. I still teach it for non-specialists and with emphasis on how to craft a technical argument and write an essay answer—skills for thesis writing in general.
I present some proofs in full and skip or “handwave” others. My full proofs highlight algorithmic ideas and logical structure. For instance, I explain how the proof that nondeterministic space is contained in deterministic time embodies breadth-first search, while nondeterministic time being in deterministic space can be treated as depth-first search. I fold together the proofs of the deterministic space and time hierarchy theorems while diagramming the offline universal simulation they embody. In proving the -completeness of I highlight how re-using variables makes a double-branch recursion into a single branch, and state what I call a “modified proverb of Lao-zi”:
A journey of a thousand miles has a step that is exactly 500 miles from the beginning and 500 miles from the end.
I skip, however, most of the proof of the simulation of a -tape Turing machine by a two-tape oblivious Turing machine . What I show is the division of the first tape into blocks of cells numbered
and the following sequence of “jags”:
Each “jag” for a number begins at cell 0, goes to , then crosses 0 on the way to cell , and returns to 0. I explain that each jag simulates one step of , and finally show or state that the total number of steps by up to the -th jag is .
I prove the theorem of Walter Savitch that nondeterministic space is contained in deterministic space , but only state the theorem that it is closed under complements. That proof I would reserve for an advanced graduate course. Overall I like to highlight a “message” in each proof, such as “software can be efficiently burned into hardware” for the simulation of Turing machines by circuits. This sets up the circuit-based version of the -completeness of , which illustrates formal verification of hardware, and subsequent -completeness theorems as showing how many combinatorial mechanisms embody formal logic in turn.
Enjoy today. If you have a moment between watching the games and eating and other activities please let us know about your thoughts on theorems vs. proofs.