Multi prover, verifier games and PCP theorem

Question

This question came up while I was going through Siu On Chan's paper on Approximation Resistance. My question is not really related to the paper though. I also guess that this is more of a reference request kind of question (preferably some lecture notes or surveys). I hope what follows helps putting the question in perspective, so please bear with me.

I recently started studying up the literature on PCPs and inapproximability and my knowledge is small. I know the proof of PCP theorem. The proof I read is Dinur's proof as presented in Arora Barak. All the while, I saw the two contrasting views of the PCP theorem

(i) the prover, verifier view and, (ii) the view related to a deciding a gap instance of a CSP (for some constant gap).

Now, my question is the following. While going through Siu's paper, I got the impression that 2 prover 1-verifier games are relevant to PCP literature. My current knowledge base is so shamelessly small that I do not really understand this. I just know the 2 views I described above and am not comfortable with the multiple provers view.

I mean, why is the value of a game with multiple provers even related to the PCP theorem where you have a single prover and a single verifier? Does the value of a game help you somehow argue about the soundness part?

Thanks

Answer 1

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>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...

Answer 2

So first, there is the class called IP, see e.g., http://en.wikipedia.org/wiki/IP_(complexity).

The trouble with verifying is, of course, that the Prover might lie. Now, imagine that you can ask two Provers, who are not allowed to talk to each other, then they might give a different answer to the same question and be caught! This class is called MIP, and is probably stronger, as IP=PSPACE while MIP=NEXP.

In fact, it can be proved that having even more Provers won't help. Moreover, we could ask a Prover to write down in advance his answers to all possible questions, turning him into an oracle. This has a similar effect to having two Provers, as to any question you get always the same answer, so the possibility of the Prover coming up with a "random lie" is eliminated.

Also a paper I just googled for: https://www.google.hu/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&ved=0CEoQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.47.1588%26rep%3Drep1%26type%3Dps&ei=CAfhUcWOFMTptQackYHoDg&usg=AFQjCNHwK437ex8iHgOwUIQ2XNAaV8l-JA&sig2=E8-RM-VGuu3htw7Nl7yNvA&bvm=bv.48705608,d.Yms