4 ms·
And the silly hardware bit flip complaint is easily addressed: run the program N times, and reduce the chance of the error by a factor that's exponential in N.
by pfdietz 7y ago
And the silly hardware bit flip complaint is easily addressed: run the program N times, and reduce the chance of the error by a factor that's exponential in N.
Large randomly generated primes are produced by a random algorithm like this, with a step that (when run on a composite number) shows that it is composite with probability p = a constant < 1. The chance of error there can also be made exponentially small.
As you say, deterministic, or at least highly correlated, errors would dominate the chance that the proof was wrong. But that's true of human proofs too.
- MaxBarraclough 7y ago> that's true of human proofs too. I'm not sure that's right. The peer review process works well (e.g. [0]) precisely because human mathematicians are likely to make (at least somewhat) different mistakes from each other. [0] https://en.wikipedia.org/w/index.php?title=Wiles%27s_proof_of_Fermat%27s_Last_Theorem&oldid=895642634#Announcement_and_final_proof_(1993%E2%80%931995) https://en.wikipedia.org/w/index.php?title=Wiles%27s_proof_o...