We show that every language in NP has a probablistic verifier
that checks membership proofs for it using
logarithmic number of random bits and by examining a
<em> constant </em> number of bits in the proof.
If a string is in the language, then there exists a proof ... more >>>