Title: Probabilistic Verification of Proofs

Recent research in the theory of computing has led to the following intriguing result. ``There exists a probabilistic verifier for proofs of mathematical assertions that looks at a proof in only a constant number of bit positions and satisfies the following properties: (Completeness) For every valid theorem there exists a proof that is always accepted. (Soundness) For invalid assertions every purported proof is rejected with some positive probability that is independent of the length of the theorem or proof.'' This result sheds insight into the fundamental complexity class NP and shows that it is equivalent to a seemingly smaller class of languages with efficient probabilistically checkable proofs. This result is especially significant to combinatorial optimization. For many combinatorial optimization problems it demonstrates that the task of finding even nearly-optimal solutions is computationally intractable. In this article we describe some methods used to construct such verifiers.

1991 Mathematics Subject Classification: 68Q10, 68Q15.

Keywords and Phrases: Computational complexity, Algorithms, Combinatorial optimization, Logic, Probability, Approximation.

Full text: dvi.gz 23 k, dvi 52 k, ps.gz 79 k.

Home Page of DOCUMENTA MATHEMATICA