Multi prover, verifier games and PCP theorem
Let me sketch the relation between the PCP theorem and 2-provers 1-round game. For concreteness let's consider the MAX-3-SAT problem. In this problem we are given a 3-CNF formula, and our goal is to find an assignment that maximizes the number of satisfied clauses. This problem is NP-hard, and (the CSP view of) the PCP theorem says that given a satisfiable formula it is NP-hard to find an assignment that satisfies 99% of the clauses.

The 2-provers 1-round game view of PCP theorem says that if we are given a game as an input it is NP-hard to distinguish between the two cases:

YES case: The provers have a strategy that always satisfies the verifier.

NO case: In every strategy of the provers will satisfy the verifier with probability at most $1-\epsilon$ for some constant $\epsilon&gt;0$.



Let us now translate the MAX-3-SAT problem into a 2-provers one round game. That is we show a reduction from MAX-3-SAT to 2P1R-game. The verifier chooses one clause from the formula and one variable from the clause at random. He sends the clause to the first prover, and the variable to the second prover. The first prover replies with an assignment to the three variables in the clause, and the second prover sends an assignment to his variable. The verifier then checks that the assignment of the first prover indeed satisfies the clause, and that the answer of the second prover is consistent with the answer of the first prover.

Now, what is left to show is that this reduction gives a gap problem for the 2-prover 1-round game.

YES case: If the given formula is satisfiable, then the provers have a strategy that will satisfy the verifier. This is easy, they just need to reply according to the satisfying assignment.

NO case: If the provers have a strategy that allows them to win with probability $1-\epsilon$, then there exists an assignment that satisfies at least $1-3\epsilon$ of the clauses. This part is also not hard to prove. Just look at the assignment of the second prover to the variables, and claim that it must satisfy at least $1-3\epsilon$ fraction of the clauses.

I hope it makes sense...