20. L and NL, NL = coNL
MIT 18.404J Theory of Computation, Fall 2020
講師: Michael Sipser
查看完整課程: https://ocw.mit.edu/18-404JF20
YouTube 播放列表: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY
Reviewed log space: NL is a subset of SPACE(log^2n) and NL is a subset of P. Introduced log-space transducers and log-space reducibility. Defined NL-completeness. Proved that PATH is NL-complete. Also proved the Immerman-Szelepcsényi theorem: NL = coNL.
執照: 知識共享 BY-NC-SA
更多信息在 https://ocw.mit.edu/terms
更多課程在 https://ocw.mit.edu
在 http 支持 OCW://ow.ly/a1If50zVRlQ
我們鼓勵在 OCW 的 YouTube 和其他社交媒體渠道上發表建設性意見和討論. 人身攻擊, 仇恨言論, 拖釣, 和不適當的評論是不允許的，可能會被刪除. 更多細節在 https://ocw.mit.edu/comments.