{\huge Thanks for Theorems and Proofs}

Which are more important? \vspace{.5in}

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 ask 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.

Our 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 $latex {\cal T}&fg=000000$ in question;
Then present the proof $latex {\cal P}&fg=000000$ of the theorem $latex {\cal T}&fg=000000$.

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 $latex {\cal T}&fg=000000$ but not the $latex {\cal P}&fg=000000$. 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.

Ken's Answers

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 ``handwave'' others. My full proofs highlight algorithmic ideas and logical structure. For instance, I explain how the proof that nondeterministic $latex {s(n)}&fg=000000$ space is contained in deterministic $latex {2^{O(s(n))}}&fg=000000$ time embodies breadth-first search, while nondeterministic time $latex {t(n)}&fg=000000$ being in deterministic space $latex {t(n)}&fg=000000$ 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 $latex {\mathsf{PSPACE}}&fg=000000$-completeness of $latex {\mathsf{QBF}}&fg=000000$ 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 $latex {O(t(n)\log t(n))}&fg=000000$ simulation of a $latex {k}&fg=000000$-tape Turing machine $latex {M}&fg=000000$ by a two-tape oblivious Turing machine $latex {M'}&fg=000000$. What I show is the division of the first tape into blocks of cells numbered

$latex \displaystyle \dots [-7,-6,-5,-4][-3,-2][-1][0][+1][+2,+3][+4,+5,+6,+7]\dots &fg=000000$

and the following sequence of ``jags'':

$latex \displaystyle 1,3,1,7,1,3,1,15,1,3,1,7,1,3,1,31,1,3,1,7,1,3,1,15,1,3,1,\dots &fg=000000$

Each ``jag'' for a number $latex {m = 2^k - 1}&fg=000000$ begins at cell 0, goes to $latex {+m}&fg=000000$, then crosses 0 on the way to cell $latex {-m}&fg=000000$, and returns to 0. I explain that each jag simulates one step of $latex {M}&fg=000000$, and finally show or state that the total number of steps by $latex {M'}&fg=000000$ up to the $latex {t}&fg=000000$-th jag is $latex {O(t \log t)}&fg=000000$.

I prove the theorem of Walter Savitch that nondeterministic space $latex {s(n)}&fg=000000$ is contained in deterministic space $latex {s(n)^2}&fg=000000$, 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 $latex {\mathsf{NP}}&fg=000000$-completeness of $latex {\mathsf{SAT}}&fg=000000$, which illustrates formal verification of hardware, and subsequent $latex {\mathsf{NP}}&fg=000000$-completeness theorems as showing how many combinatorial mechanisms embody formal logic in turn.

Open Problems

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.