Does Raghav = co-Raghav?
Classically, our ancestors observed that RE ≠ co-RE, and more recently, Immerman-Szelepcsényi showed that NL = co-NL. Based on this evidence, one might conclude that Raghav = co-Raghav question is a toss-up. We now show that this is not the case. We appeal to certain folklore results from the literature.
Suppose Raghav = co-Raghav were a toss-up. Consider the following nondeterministic algorithm:
let Raghav = Raghav + 1
nondeterministically guess Raghav
if found
let p = p - 2
else
output "How fat is she?"
end(if)
Clearly, the language accepted by this program is irrelevant to the question. There is no doubt about it. Stay tuned.
2 Comments:
Umm ... I have always been convinced that Raghav=co-Raghav. Maybe I'm wrong.
Parinya
You are partially right, raghav is closed under complementation, just like NL.
but the proof will not be by inductive counting as in case of NL.
one side as usual is obvious:
anything that does not belong to me does belong to me indeed (like jason's hat!)
the other side requires a lot of hard work
and i wont be able to give the details here
raghav
Post a Comment
<< Home