FOM: Conclusiveness of Proofs IV

[JSHIPMAN@bloomberg.net]

Despite my caveats in my third posting on this subject, there remains a strong
argument in the case of statements of the form "n is prime" that we can
"decide" these statements in a feasible way by a randomized algorithm but we
don't know how to do it feasibly by a classical algorithm (which would
necessarily generate a classical proof, namely the trace of the feasible
classical computation along with the ordinary once-for-all proof that the
algorithm was correct).  There is an "almost polynomial time" deterministic
algorithm for deciding {primes}, but other sets in "random polynomial time" may
not be so easy to decide.  The situation reminds me of the (mathematical!)
challenge "prove that if you remove Black's Queen in the initial position of a
chess game White has a forced win"--here we are extremely far from anything
like a mathematical proof but any chess expert is more certain this is true
than any number theorist is certain there isn't still a hidden mistake
somewhere in Wiles's proof.  The analogy is imperfect because with an "n is
prime" statement we can do better since we have a probabilistic bound.-J Shipman