I'm studying for an exam, and one of the practice questions is this:
Assume an polynomial probabilistic algorithm exists for an NPC decision problem $A$. For a yes-instance it gives the right answer 80% of the time and for a no-instance 70% of the time. Can we conclude that $NP \subseteq BPP$?
And the answer is:
False, this cannot be concluded based on the above, and in general it is not known whether $NP \subseteq BPP$.
I came to the conclusion it was true, and I (together with a peer) can't figure out what I did wrong:
$A \in BPP$ since we have this algorithm (confirmed by one of the other questions / answers).
Since $A \in NPC$, every problem $X \in NP$ can be reduced to $A$. Then, if we run this algorithm, it will have the correct answer at least 80% (or 70%) of the time. Thus, every problem in $NP$ can be solved this way, thus there is a probabilistic algorithm for all $X \in NP$, thus $NP \subseteq BPP$.
My reasoning is obviously incorrect, because the assumption is true (I know such an algorithm for 3SAT), but "the relation between $NP$ and $BPP$ is not known" - wikipedia