Stop Teutsching Me

A blog about Raghav Kulkarni and other interesting subjects.

Friday, March 10, 2006

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
output "How fat is she?"

Clearly, the language accepted by this program is irrelevant to the question. There is no doubt about it. Stay tuned.


Anonymous Anonymous said...

Umm ... I have always been convinced that Raghav=co-Raghav. Maybe I'm wrong.


March 11, 2006 7:16 PM  
Anonymous Anonymous said...

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


March 12, 2006 5:51 PM  

Post a Comment

<< Home

Google Web