0
$\begingroup$

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

  • 0
    since NLogSpace=CoNLogSpace, i think both the statements are true... but is is true to say that ConNLogSpace=NLogSpace??2012-01-10

1 Answers 1

1

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.

  • 0
    so that means both the statements are true?2012-01-11