Friday, September 15, 2017

Day 10

Today we covered the complements of languages and co-classes and did most of the proof of the Immerman-Szelepcsényi theorem that non-deterministic space is closed under complement. In particular we focused on the proof that NL = co-NL


  • The complement of a language L, denoted L, is the set of strings not in L.
  • For a complexity class C, we define co-C as the set of languages L for L in C.