I am asking myself the following:
When can we say that a Monte Carlo algorithm solves a problem?
To quote from Wikipedia on Monte Carlo algorithms
For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least ½ and true with probability less than ½.
What would happen if the Solovay–Strassen Test would answer true for only 1% of composite inputs? Would we than still say that it solves the problem of testing primality? Or is there some requirement like that a Monte Carlo algorithm has to answer true for more than half the cases?