patternModerate
Why is $BPP$ closed under complement?
Viewed 0 times
whyclosedunderbppcomplement
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#28036, answer score: 18
Revisions (0)
No revisions yet.