Comment Re:Comparing Apples to Apples (Score 1) 171
Let's say the probability is 1/2. The solution to the system can be verified in polynomial time. If the solution is incorrect, run the algorithm again.
After you run it N times, the probability of error is 1/(2^N), and you only wasted polynomial time on verification. Clearly, when your probability of error is smaller than the cardinality of possible outcomes, the algorithm will perform as designed in a sane amount (polynomial) of time.