We will first look at different view of NP. NP can be viewed as a game where the (all powerful) prover is trying to convince a (poly time) verifier that (say) a formula is satisfied. We generlize this and look at different ways the prover and verifier can interact. In later lectures (given by others) this will lead to non-approx results like: If you can approximate CLIQUE very well then P=NP.