I didn't know that paper. That is a fun result. It reminds me a bit of the miller-rabin test for prime numbers. This test checks how probably it is that a number is a prime.
You are viewing a single comment's thread from:
I didn't know that paper. That is a fun result. It reminds me a bit of the miller-rabin test for prime numbers. This test checks how probably it is that a number is a prime.
isn't on the list, then we'll make only finitely many mistakes.To me it feels a little bit like Levin's universal search (https://www.quora.com/How-is-it-possible-that-an-existing-algorithm-solve-NP-complete-problems-in-polynomial-time-if-and-only-if-P-NP/answer/Mark-Gritter) in that it keeps ticking things off an infinite list. If the right answer's there, then we'll get to it eventually. The clever bit is ensuring that if the mean value