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.
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 isn't on the list, then we'll make only finitely many mistakes.