Computability and Complexity (Spring 2015)

Shay Mozes

Lectures (including video)

L01 Overview, Turing Machins [Video]
L02 Decidable and recognizable languages, the Church-Turing thesis, variants of TMs [Video]
L03 Existence of unrecognizable languages, universal TMs, towards reductions [Video]
L04 Mapping reducitons, some undecidable/unrecognizable languages [Video]
L05 Rice's theorem, Post's correspondence problem [Video]
L06 Time complexity, the class P, verifiers, the class NP [Video]
L07 The class NP, Non-deterministic TMs, P=NP? [Video]
L08 Polynomial time reductions, NP-completeness [Video]
L09 The Cook-Levin theorem, more NP-complete problems [Video]
L10 Cook/Karp/Levin reductions, decision vs. search, space complexity [Video]
L11 More space complexity, dealing with NP-hardness, approximation algorithms [Video]

Infrastructure for this site and for making the videos available was generously provided by Erik Demaine.