Why is $\text{BPP}=\text{co-BPP}$?
I tried to find a proof online but couldn't.
Can anyone please provide a quick explanation (if it's trivial and I just can't see it) or a link to a proof?
Asked By : so.very.tired
Answered By : D.W.
It follows directly from the definition of BPP.
The definition says that a problem with a yes-or-no answer is in BPP if there is a randomized algorithm that gets the correct answer with probability $\ge 2/3$ on all possible instances. This means that on all instances where the correct answer is YES, the algorithm has to output YES with probability at least $2/3$; and on all instances where the correct answer is NO, the algorithm has to output NO with probability at least $2/3$.
Therefore, if a problem $P$ is in BPP, its negation is also in BPP. Take the algorithm for $P$, and just flip its output. That will be a valid algorithm for the negation of the problem.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28036
0 comments:
Post a Comment
Let us know your responses and feedback