Other things can be added like Primitive Recursive Functions, the arithmetic hierarchy, the polynomial hierarchy.
I am considering NOT proving Cook's Theorem. State it YES, say how important it is YES, but prove it NO. I am not sure if I want to do this. This post is an attempt to get some intelligent comments on this. My mind is not made up yet so this is I raise the question TRULY non-rhetorically. Some thoughts:
- The proof is coding a Turing Machine computation into a formula. It is interesting that you can do this. The details of it are not so interesting.
- The very good students (I would guess 5 out of my 40) will get it. The bad students never get it. I am oversimplifying--- and if this was a reason to not teach a topic I may not have much of a course left.
- The time spend IN CLASS on this is not so much- one lecture. The time spend in OFFICE HOURS on this re-explaining it is a lot. And its not clear that it helps.
- Showing them NPC reductions is more important and more interesting. This is what I would put in instead. I usually only get to do a few.
- Cook's Theorem is SO fundamental that the students should SEE a proof of it even if they don't understand it. but I am not a fan of they should see it even if they don't understand it.
- Cook's Theorem, like many things, you don't get the first time you see it, but you do the second, helped by having seen it once.
- Even if we now they mostly won't get it, we want them to know that we WANT them to get it.
- Students should know that the proof that SAT is NP-complete goes all the way back to the machine model (very few other NP-completeness proofs do). Is it good enough to TELL them this. I would DEFINE Turing Machines, SAY that you CAN code a computation into a formula, but not actually do it?
- I like to teach things that I can ask problems about. Cook's theorem IS okay for this- I usually show how to make a formula out of some TM instructions and leave as HW making a formula out of other TM instructions. Even so, not that much can be asked about it. The students have a hard time with this (Much more so than other parts of the course) so I wonder if its too much sugar for a cent.
- I teach this course a lot so I want to mix things up a bit. I realize this is not really a good reason for the students.
- An argument for: See how it goes! The decision I make this semester need not be what I always do.