Lecture 21: Hierarchy Theorems

Name: Lecture 21: Hierarchy Theorems
Uploaded: 2021-10-06T12:44:33Z
Duration: 1 h 21 min 57 s
Description: 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

1:21:57

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