Lecture 21: Hierarchy Theorems

Om kurset

Description: Quickly reviewed last lecture. Finished Immerman-Szelepcsényi theorem: NL = coNL. Introduced and proved the time and space hierarchy theorems. Discussed using the hierarchy theorems to separate certain complexity classes. Instructor: Prof. Michael Sipser