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

Definitions:

• 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.

Links:

• My writeup of Immerman-Szelepcsényi
• Nondeterministic Space is Closed under Complementation by Neil Immerman
• The method of forced enumeration for nondeterministic automata by Róbert Szelepcsényi