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:
- Randomized and interactive verification procedures,
giving rise to interactive proof systems,
seem much more powerful (i.e., more ``expressive'')
than their deterministic counterparts.
These probabilistic proof systems demonstrate
the advantage of interaction (over one-directional communication).
- Such randomized procedures allow for
the introduction of zero-knowledge proofs,
which are of great theoretical and practical interest.
These probabilistic proof systems demonstrate the
possibility of decoupling proving from learning
(i.e., the possibility of proving an assertion
without yielding anything beyond its validity).
- NP-proofs can be efficiently transformed into a (redundant) form
(called probabilistically checkable proofs)
that offers a trade-off between the number of locations examined
in the NP-proof and the confidence in its validity.
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