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