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
Asked
Active
Viewed 551 times
0
-
Try to show us what you have tried instead of making it look like you are giving us a homework assignment. – sxd Jan 10 '12 at 19:31
-
since NLogSpace=CoNLogSpace, i think both the statements are true... but is is true to say that ConNLogSpace=NLogSpace?? – Blue Devil Jan 10 '12 at 20:03
1 Answers
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.
David Moews
- 16,651