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.
"Of course power tools and alcohol don't mix. Everyone knows power tools aren't soluble in alcohol..." -- Crazy Nigel