class of probabilistically checkable proofs. Recall that NP can be seen as the class of problems where an all-powerful prover gives a purported proof that a string is in the language, and a deterministic polynomial-time machine verifies that it is a valid proof. We make two changes to this setup:

* Add randomness, the ability to flip coins, to the verifier machine.
* Instead of simply giving the purported proof to the verifier on a tape, give it random access to the