1
$\begingroup$

I had an exam, and one of the questions was Does ZPP = BPP if coNP ⊆ ZPP. I came down to coNP ⊆ NP and went on with "then coNP = NP", am i right?

$\endgroup$

1 Answer 1

6
$\begingroup$

Yes. Assume co-NP ⊆ NP. Take any NP problem. Its complement is co-NP, therefore NP by co-NP ⊆ NP, so the problem itself is co-NP, QED.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.