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.

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?

• Define needed terms;

• State the theorem ${\cal T}$ in question;

• Then present the proof ${\cal P}$ of the theorem ${\cal T}$.

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 ${\cal T}$ but not the ${\cal P}$. 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 ${s(n)}$ space is contained in deterministic ${2^{O(s(n))}}$ time embodies breadth-first search, while nondeterministic time ${t(n)}$ being in deterministic space ${t(n)}$ 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 ${\mathsf{PSPACE}}$-completeness of ${\mathsf{QBF}}$ 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 ${O(t(n)\log t(n))}$ simulation of a ${k}$-tape Turing machine ${M}$ by a two-tape oblivious Turing machine ${M'}$. What I show is the division of the first tape into blocks of cells numbered

$\displaystyle \dots [-7,-6,-5,-4][-3,-2][-1][0][+1][+2,+3][+4,+5,+6,+7]\dots$

and the following sequence of “jags”:

$\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$

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

I prove the theorem of Walter Savitch that nondeterministic space ${s(n)}$ is contained in deterministic space ${s(n)^2}$, 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 ${\mathsf{NP}}$-completeness of ${\mathsf{SAT}}$, which illustrates formal verification of hardware, and subsequent ${\mathsf{NP}}$-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.

1. November 24, 2016 2:33 pm

I think a general rule is this; “short and simple proof should not be skipped”.
If the length of the proof has been shown to be unavoidably long then state only theorem and mention the proof with a few lines. On the other hand if the statement of the theorem “simple” and known proof is very lengthy then the question whether there exits a shorter and readable proof is more important even the theorem itself. Here is my favorite theorem.

Theorem: All planar graphs are four colorable.

Can you skip the proof?

My short “proofs” of this theorem have been outlined here:

November 24, 2016 5:52 pm

In teaching a standard automata and language theory class based on Sipser’s text to rather ordinary undergraduate students, I would teach them how to transform nondeterministic automata to deterministic automata to regular expressions, etc., and I think that being able to perform these equivalence transformations was as helpful to them as being able to do the proofs of equivalence.

3. November 25, 2016 12:07 am

I think it depends on the pedagogic value of the proof. If the proof illustrates some useful technique or some significant idea, then as a student, I’d want to see it.

Some proofs may not add much to students in their current state of knowledge. Those might be given as extra reading.

4. November 25, 2016 4:55 am

If the proof helps student understand the theorem then give the proof. If the proof is very long or has non-illuminating lemmas, give an outline.

If the proof is clever and short, give the proof.

I think you have to ask why (like you are in fairness) are you presenting a long proof that doesn’t help student understand the theorem. Of course there are reasons to and reasons not to.

5. November 25, 2016 12:34 pm

one of the great dichotomies of math, thms vs proofs. am sure you guys kind of already know the answer, but anyone who wants to become a mathematician themself has to learn how to prove stuff, and even come up with their own proofs, aka “get under the covers”. everyone else can be treated as something of a “consumer” of mathematics. surely others have noticed this, theorem statements are a bit like APIs in software. you can use the software just understanding the API. but somebody had to “write the code”. its cool that its reusable by others who dont understand all the code. it is neat that sometimes very complex proofs can still be understood by others by their results alone.

6. November 25, 2016 12:37 pm

ps re the spirit of the blog/ seasonal event, thx for the great blog & taking the obviously substantial time to write it! am thankful for the few blogs around by top experts sharing their copious experience/ talent for free! 🙂

7. November 25, 2016 12:59 pm

Mathematicians say to their students: if you don’t know proof, then you don’t know the theorem! But a programmer needs no proof to use any theorem 🙂

Happy holiday to you!

November 27, 2016 10:06 am

Theorems should be explained, but they can be explained without the use of a proof. For example, when teaching the Pythagorean theorem for the first time, most teachers do not give an in depth proof, but they will draw out squares and explain what the theorem means.

November 27, 2016 6:52 pm

I always wonder if using a variant of the Moore method of teaching, famous in mathematics; used by mathematicians like Paul Halmos, would be effective.
During the lecture, the professor presents definitions,ideas and theorems but instead of making the students prove statements, the professor could assign them as homework assignments. Group work should be encouraged for these, since that allows students to debate and learn more!

Hope the turkey was full of gravy and Thanksgiving was great! THWg!

• November 28, 2016 3:49 pm

Copy and paste wouldn’t be allowed.