MIT
Lecture 20: L and NL, NL = coNL
Data Science, Analytics & Computer TechnologyComputer ScienceScience & MathMathematicsEngineering
Om kurset
Description: Reviewed \(\log\) space: NL ⊆ SPACE\((\log^2n)\) and NL ⊆ P. Introduced log-space transducers and log-space reducibility. Defined NL-completeness. Proved that \(PATH\) is NL-complete and \(\overline{2SAT}\) is NL-complete. Proved the Immerman-Szelepcsényi theorem: NL = coNL. Instructor: Prof. Michael Sipser