If a mathematical proof can be lengthy, verifying its validity may turn out to be almost as complex. Sudan offers a brief review of an alternative procedure to analyze mathematical proofs, using probabilistic algorithms. His explanation focuses specifically on the complexity of the query and the probability gap of certainty for accepting or rejecting a proof as a valid one.

The article touches on the question of whether a proof can be checked efficiently, in polynomial time in the length of its shortest proof, and also if such a proof--mathematical or any other formal abstraction--can be queried about its validity, in probabilistic fashion, with the least possible questions. The article makes some progress toward answering such questions, although a probabilistic verifying algorithm that is of real practical use for mathematicians is still to be worked out.

The topic of probabilistic checkable proofs is indeed important, and Sudan’s article and the references therein should be studied by any pure mathematician who is working on provability. I would also recommend this paper to computer scientists who are dealing with problems related to proving the internal coherence of systems, especially if they are dependent on some form of combinatorial optimization.