I am confused by the definition of probabilistic checkable proofs.

Language $L$ has an $(r(n),q(n))$ - PCP verifier, if there is a PPA V satisfying:

Efficiency: $V$ uses at most $r(n)$ random coins and makes at most $q(n)$ nonadaptive queries to location of $\pi$.

Completeness: $x \in L, \exists \pi \in \{0,1\}^*, Pr[V^{\pi}(x)=1]=1$

Soundness: $x \notin L, \forall \pi \in \{0,1\}^*, Pr[V^{\pi}(x)=1]\leq\frac{1}{2}$

The main question:

  • Why does PCP need randomness?
  • How exactly are random coins used in the PCP?
  • And what happens when these random coins are actually deterministic?
  • Where does the effective proof length bound of $2^{r(n)}q(n)$ come from?
  • $\begingroup$ I have no answer for you, but this reads as if you should closely re-read the definition, motivating text in a textbook and a couple of theorems. $\endgroup$ – Raphael Jun 21 '13 at 6:20
  • $\begingroup$ @Raphael, you are right, but it still doesn't make sense for me. As I understand, $r(n)$ random coins define a specific location between $0..2^{r(n)}$, only one location, how $r(n)$ can encode several locations, $q(n)$ number of queries to the same proof witnesses $\pi$, or it's just $q(n)$ different $\pi$'s. $\endgroup$ – com Jun 21 '13 at 11:20

The way a PCP works is like so: in order to verify some property, the prover presents a proof P which is "easily testable". The way to test it is to query the proof at a small number $q(n)$ of points. We want the PCP to satisfy two properties:

  1. If the property actually holds, the verifier should always (or almost always) accept.
  2. If the property doesn't hold, then the verifier would notice with some constant probability.

Now if the proof is long and the verifier only looks at a small number $q(n)$ of them, then they better be random! Otherwise it's very easy to fool the verifier. That should answer your first and third questions.

How are the random coins used? In an arbitrary way. The verifier chooses $r(n)$ random coins, and based on them queries the proof at $q(n)$ points. Then she applies a test which always succeeds in YES instances (the property holds), but fails with constant probability (over the coin tosses) in NO instances (the property doesn't hold). That should answer the second question.

Since there are $r(n)$ coins, there are $2^{r(n)}$ different outcomes for the coins, and so the verifier in total queries the proof in at most $2^{r(n)}q(n)$ different places. That answers your fourth question.

What's the point of a PCP? We can encode the verifier as a CNF whose variables are the bits of the proof: for each of the $2^{r(n)}$ coin tosses, there are clauses encoding that the $q(n)$ bits sampled pass the verifier's test. If it's a YES instance, then this CNF is satisfiable. If it's a NO instance, then the verifier fails with some constant probability, and so a constant fraction of the clauses in the CNF are always unsatisfied.

The PCP theorem gives a PCP for 3SAT with $q(n) = O(\log n)$ and $r(n) = O(1)$. That means that given a 3CNF, we can come construct a new CNF of length $O(2^{q(n)}) = n^{O(1)}$ using the construction outlined in the preceding paragraph such that (i) if the original 3CNF formula is satisfiable, so is the new one, (ii) otherwise, at most $1-\epsilon$ fraction of the clauses can ever be satisfied in the new CNF. That gives a hardness of approximation result for 3SAT.

Using Raz's parallel repetition theorem, Håstad obtained a construct in which in case (ii), at most $7/8+\epsilon$ of the clauses can be satisfied, thus obtaining an optimal inapproximability result. (It's optimal since a random assignment satisfies $7/8$ of the clauses; this algorithm can be derandomized using the method of conditional expectations.)

  • $\begingroup$ There are $2^{r(n)}$ different outcomes for the coins, but what they are in terms of prover? Are they just locations on the $\pi$, if so that $|\pi| \leq 2^{r(n)}$. "the verifier in total queries the proof in at most $2^{r(n)}q(n)$ different places." - but they are just $q(n)$ queries, at most it can query $\pi$ in $q(n)$ different places. What I get wrong? $\endgroup$ – com Jun 21 '13 at 7:50
  • $\begingroup$ The places which get queried depend on the coin tosses. For each of the $2^{r(n)}$ coin tosses, there are $q(n)$ places that get queried, so in total there are at most $2^{r(n)}q(n)$ places that get queried. For example, perhaps $q(n) = 3$ and the places that get queried are $3R,3R+1,3R+2$, where $R \in [2^{r(n)}]$ are the random bits. $\endgroup$ – Yuval Filmus Jun 21 '13 at 13:34
  • $\begingroup$ Does it mean that $R$ just identify the location of the first symbol to read, and $q(n)$ identifies how many consecutive symbols starting from $R$ should the verifier read? $\endgroup$ – com Jun 21 '13 at 14:25
  • $\begingroup$ No, $R$ is just a string of length $r(n)$, and the verifier can do with it whatever she wants. For example, if $R = 0$ she could read bits $10,56,78$, and if $R = 1$ she could read bits $13,102,55555$. It's completely up to her. Another example: the verifier can use her random bits to sample a few (possibly correlated) random positions (that's more similar to what actually happens in PCPs). $\endgroup$ – Yuval Filmus Jun 21 '13 at 15:08
  • $\begingroup$ Oh, understood, so the "mapping logic" is up to verifier, and not known to us. I thought that we know the logic. $\endgroup$ – com Jun 21 '13 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.