Smashed on the Shoals of P/NP
…where hubris has driven many before me.
So for a while I’ve been wondering, “Is it possible teach P/NP to introductory CS students?” Taking as a starting point that your students understand Big O, it’s not difficult to get to the definitions (assuming you are willing to call NP the set of polynomial time verifiable problems). But that always seemed to be a cop out, because it really ignores what I think is the actual neat part of P/NP – the fact that NP-complete problems exist. For that you need Cook’s theorem, and that is a sticky wicket indeed.
I’m taking a course on education this semester, and we have to build a couple lesson plans. So, just for fun I decided to try to see if it could be done.
Foolish foolish me. I just got an email from my professor saying that a) she had no idea what my lesson was about and b) it would likely need to be re-worked considerably if I was going to get credit. Not exactly what you like to hear after you’ve already devoted more time than you really should to a project. Not that I can really disagree – it’s just too much for one lesson I think, no matter how you cut it.
So I’m gonna rework it to just talk about P/NP and not Cook’s theorem. You all can feel free to mock me. Even though I really think my extended Sudoku example is cool, and there’s really no point to it if you don’t do Cook’s theorem. But just for posterity’s sake I’m tossing up my slides (scroll to the end to see my sketchy notes) and handout. If you can think of any shortcuts that I missed, do pass it along. Or theoretically unconscionable mistakes…anyone who reads this blog knows I’m not much of a theorist.
Maybe if I completely reworked it to start with Cook’s theorem, and then moved to P/NP from that…it really could be done, maybe. But I’ve got no more time for more time sacrificed to pride right now.
I think your slides are reasonable, but of course I don’t have a handle on your intro students’ background. Probably a good idea to scale it back a bit to fit in a single lecture.
My own intro CS course included a fairly complete treatment of complexity classes and NP-completeness, but it was spread out over most of a semester. (The class was taught by a really great lecturer, Ran Libeskind-Hadas, whose own research includes a lot of NP-completeness proofs.) We came at the topic from a different direction: we started by studying finite automata (DFAs and NFAs) and regular languages, then extended that to Turing machines, then introduced P and NP in terms of deterministic and nondeterministic Turing machines.
We also emphasized the fact that reducing a problem to *any* known NP-complete problem (not just SAT) proved that the original problem was NP-complete. (For example, it’s often easier to reduce a graph problem to another graph problem than to SAT.) I think this might provide an easier way for you to illustrate NP-completeness without diving into the mechanics of Cook’s theorem. I’m not sure how to briefly explain what I mean, but you can email/call/chat if you want me to elaborate.
One possible minor omission in your slides: It’s very important that the reduction step itself (“reduce a verifier to a boolean equation”) can be shown to be a polynomial time algorithm. (Also the mapping back to the original domain.)
In the notes you mention, “you stand to get a million dollars.” You should make sure to include that this literally true. Mention the Clay Prize website, where curious students can learn about the other million-dollar problems.
Tangentially, have you read the Sudoku functional pearl? There are some accompanying slides and source code on the Haskell wiki.
That would have been a pretty interesting intro class.
The audience for this is more-or-less hypothetical at this point but I envisioned a knowledge of Big O but none of the more theoretical stuff like DFAs and NFAs. I mean, certainly if you’re going to teach P/NP for real, that’s the way to do it. But it’s more than a class worth of material then, which is I figure more than a CS instructor focused on the basic ins-and-outs of programming would like to spend.
I introduced Cook’s theorem not so much to talk about reducibility as to (semi-)prove the existence of NP-Complete problems in the first place. If I really want to prove that, I need to talk about a problem that is NP-Complete…um….naturally I guess. That is not due to its reducibility to any other problem. Or maybe I need more elaboration to see how this explanation you’re thinking of goes.
But I think it’s a fair point that in all honesty a) students would probably be willing to take my word for their existence b) reducing one NP complete problem to another is in some sense the one real practical skill in this whole P/NP maelstrom, and wouldn’t it be nice to at least mention it in passing. The revised version of my slides does this, sort-of, but in all honesty it happens so fast and with no reinforcement so it almost might-as-well not be there at all.
It may be the case that I actually get to test the shortened version of this lecture…I’ll be interested to see how it goes. It would very much please me if I could put a little more content back in. But I suppose it’s always better to start by teaching 75% of the material successfully than 100% unsuccessfully.
Tangentially, that Haskell stuff is slick. Consider Haskell moved up on the “Technologies Mike Is Ashamed not to be Familiar With” list.
Yeah, that was exactly my idea for a shortcut: Make it an article of faith (for now) that at least one NP-complete problem exists. Then you can show that a polynomial-time reduction from NP problem X to NP-complete problem Y shows that X is NP-complete. And you can give some examples of which problems have been reduced to which other problems.
Then (maybe in a later lecture?) you can introduce Cook’s theorem. The motivation might be more obvious at that point, since it gives you the missing “first” NP-complete problem to form the root of the family tree.