The previous lecture in this series is here. The next lecture in this series is here.
Quickly reviewed last lecture. Defined NTIME(t(n)) complexity classes and the class NP. Showed that COMPOSITES is in NP. Discussed the P versus NP question. Proved that acceptance problem for CFG is in P. Introduced the satisfiability problem SAT and polynomial-time reducibility.
These videos are of a lecture course by Michael Sipser at the Massachusetts Institute of Technology in 2020, and made available as part of its OpenCourseWare initiative.