### 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