0

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

Ivo
  • 101
  • I don't know anything about this but I don't understand how an algorithm that has a 20% chance of being wrong can be used to produce a solution. – DanielWainfleet Apr 17 '18 at 22:03
  • by running it multiple times, it is possible to get the chance arbitrarily close to the correct answer.
  • For some problems finding the solution is really hard, but verifying whether something is a solution can be done pretty quickly. So you could use a probabilistic algorithm to find a possible solution and then verify it with a deterministic algorithm.
    • – Ivo Apr 17 '18 at 22:12