PCP - prover commits to long proof that verifier can spot check randomly. Invented by Arora and Safra

Proof complicated - uses multilinear testing combined with special error correcting codes.

Applications to optimization problems, particularly MAXSNP class of Papadimitriou and Yannakakis