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.