FOM: Conclusiveness of Proofs III

[jshipman@bloomberg.net]

In my second post on this subject I raised the possibility of an alternative to
"classical" proofs using randomized algorithms or "interactive proof systems"
(a generalization of randomized algorithms where a "prover" who has access to
either extra computational power or secret "trapdoor" information can convince
a "verifier" of the truth of some mathematical fact in a feasible (to the
verifier) way without necessarily exhibiting a "classical" proof).  The
mathematical facts involved here are FINITE statements that are verifiable in
principle, but not necessarily feasibly--by accepting a probability of error
whose log is polynomially bounded the verifier achieves "moral certainty".  This
represents a genuine expansion of the notion of proof only if certain unsolved
conjectures from computer science are true (you need P~=PSPACE to begin with).
Further, in the "trapdoor" case the "prover" has a classical proof so we can
justifiably demand outside the cryptographic context that he give it; while the
"extra computational power" case seems unrealistic (I'll argue in a later
posting that is isn't necessarily).                    -- Joe Shipman