Cheap and Secure Web Hosting Provider : See Now

Why closedness of complement of randomized classes imply containment of complement of contained classes?

, , No Comments
Problem Detail: 

Suppose if class $\mathcal C$ is in $PP$ or $BPP$ does it mean complement also belongs to $PP$ or $BPP$ respectively? Does it immediately follow from $PP=coPP$?

Asked By : Turbo
Answered By : Ariel

Yes, you should follow the definitions, if $L\in \mathcal{C}\subseteq PP$, then $\overline{L}\in PP$. It immediately follows that $co-\mathcal{C}=\{L | \overline{L}\in \mathcal{C}\}\subseteq PP$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55944

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback