2 ms·
I bet I could take a few moments and come up with a proof that such a method would require P=NP.
by baddox 12y ago
I bet I could take a few moments and come up with a proof that such a method would require P=NP.
- dtech 12y agoI can't find an authoritative source on this, but the algorithm used by SuperPi: https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorit... seem polynomial in the number of digits you want to calculate at first glance.
- baddox 12y agoEven if that's the case, wouldn't the number of digits of pi that must be computed to find a n occurrence of a random bit string of length n not be polynomial in n?