Meeting 4.1: Complexity

I continue to review some of the usual suspects in complexity: P, NP, PSPACE, EXP and such. I then introduce two basic notions of reduction: polynomial-time many-one reductions (aka Karp reductions) and polynomial-time Turing reductions (aka Cook reductions).  I conclude with some examples of NP-complete problems, including a first example from knot theory: the sub-unlink recognition problem.