Assume S1, S2∈ NLOGSPACE. Which of the following statements is true? • S1 \ S2 ∈ coNLOGSPACE • S1 Δ S2 ∈ NLOGSPACE
where A\B is the set of members of A that are not members of B. And A Δ B is the set of members of A U B that are not members of A ∩ B
Assume S1, S2∈ NLOGSPACE. Which of the following statements is true? • S1 \ S2 ∈ coNLOGSPACE • S1 Δ S2 ∈ NLOGSPACE
where A\B is the set of members of A that are not members of B. And A Δ B is the set of members of A U B that are not members of A ∩ B
The Immerman–Szelepcsényi theorem says that NLOGSPACE is closed under complementation. So, if S1 and S2 are in NLOGSPACE, S1 \ S2 = S1 ∩ S2$^c$ and S1 Δ S2 = (S1 ∩ S2$^c$) ∪ (S1$^c$ ∩ S2) are both in NLOGSPACE. Since NLOGSPACE is closed under complementation, NLOGSPACE=co-NLOGSPACE, so they are also in co-NLOGSPACE. The link contains a sketch of a proof of the Immerman–Szelepcsényi theorem.