Probabilistic Proof Systems

an attempt at a popular presentation


Traditional proof systems, ans specifically NP-proof systems, are defined in terms of deterministic verification procedures. However, we can gain a lot if we are willing to take a non-traditional step and allow probabilistic verification procedures. In particular:

In all the aforementioned types of probabilistic proof systems, explicit bounds are imposed on the computational complexity of the verification procedure, which in turn is personified by the notion of a verifier. Furthermore, in all these probabilistic proof systems, the verifier is allowed to toss coins and rule by statistical evidence. Thus, all these proof systems carry a probability of error; yet, this probability is explicitly bounded and, furthermore, can be reduced by successive application of the proof system.

Material available on-line


Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers