FOM: probabilistic rigor
JoeShipman at aol.com
Sat Oct 17 13:14:39 EDT 1998
It is strange that Odlyzko doesn't recognize the significance of the
difference between the two notions of "probabilistic proof". The best way I
can think of to make the difference clear to him is to find an example of a
numerical predicate whose frequency is closely approximated by a formula for
numbers in a feasible range but greatly diverges from it afterwards. Can
anyone suggest a natural example?
I am not sure primality tests are quite as practically feasible as you claim.
There is a deterministic "almost polynomial time" (exponent is loglog of the
input size rather than constant) algorithm and a probabilistic one which fits
your description (never makes an error and *usually* runs quickly) whose worst
case is "almost polynomial time" but with a better constant in the exponent
than the deterministic case, but the *usually* means "always for most inputs"
rather than "most of the time for all inputs". There is also a test which
runs in polynomial time with randomized input which has an exponentially small
probability of error, and a test which runs in polynomial time and is always
correct if the Extended Riemann Hypothesis is true. But I am not aware that
there is a test for which it has been unconditionally proven that
1) it never makes an error
2) there is a polynomial P such that for *any* input to be tested for
primality, the probability it does not finish within P(inputsize) steps is
Such an algorithm would certainly be the next best thing to a true P-time
algorithm; but can you give me a reference that such an algorithm actually
exists for testing primality?
More information about the FOM