8
$\begingroup$

I am a mathematician working toward understanding a proof the the PCP theorem using Arora and Barak's textbook Computational Complexity. I believe I found a few (fixable) errors in Section 22.2, in the part titled "Proving Theorem 11.5 from Lemma 22.4", but I am not sure I completely understand. As I stated two years ago, I still can't find any errata list that is very comprehensive.

I will copy their proof here (page 462 in my book) and then post my questions afterwards. Things I add are in brackets.

Note that I first posted this question here at cs.stackexchange over a week ago and got no answers. I then asked on meta if it was appropriate for this site.


Recall that for a $q_0$CSP-instance $\varphi$, we define $\operatorname{val}(\varphi)$ to be the maximum fraction of satisfiable constraints in $\varphi$.

Their proof:

Definition 22.3 Let $f$ be a function mapping CSP instances to CSP instances. We say that $f$ is a CL-reduction (short for complete linear-blowup reduction) if it is polynomial-time computable and, for every CSP instance $\varphi$, satisfies:

  • Completeness: If $\varphi$ is satisfiable then so is $f(\varphi)$
  • Linear blowup: If $m$ is the number of constraints in $\varphi$, then the new $q$CSP instance $f(\varphi)$ has at most $Cm$ constraints and alphabet $W$, where $C$ and $W$ can depend on the arity and the alphabet size of $\varphi$ (but not the number of constraints or variables).

Lemma 22.4 (PCP Main Lemma) There exist constants $q_0 \geq 3$, $\epsilon_0 > 0$, and a CL-reduction $f$ such that for every $q_0$CSP-instance $\varphi$ with binary alphabet, and every $\epsilon < \epsilon_0$ the instance $\psi = f(\varphi)$ is a $q_0$CSP [instance] (over [a] binary alphabet) satisfying $$ \operatorname{val}(\varphi) \leq 1 - \epsilon \implies \operatorname{val}(\psi) \leq 1 - 2\epsilon$$

Proving Theorem 11.5 from Lemma 22.4 Let $q_0 \geq 3$ [and $\epsilon_0 > 0$] be as stated in Lemma 22.4. As already observed, the decision problem $q_0$CSP is NP-hard. To prove the PCP Theorem we give a reduction from this problem to GAP $q_0$CSP. Let $\varphi$ be a $q_0$CSP instance. Let $m$ be the number of constraints in $\varphi$. If $\varphi$ is satisfiable, then $\operatorname{val}(\varphi) = 1$ and otherwise $\operatorname{val}(\varphi) \leq 1 - 1/m$. We use Lemma 22.4 to amplify this gap [assuming $1/m$ isn't big enough]. Specifically, apply the function $f$ obtained by Lemma 22.4 to $\varphi$ a total of $\log m$ times. We get an instance $\psi$ such that if $\varphi$ is satisfiable, then so is $\psi$, but if $\varphi$ is not satisfiable (and so $\operatorname{val}(\varphi) \leq 1 - 1/m$), then $\operatorname{val}(\psi) \leq 1 - \min\{2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0$. Note that the size of $\psi$ is at most $C^{\log m} m$, which is polynomial in $m$. Thus we have obtained a gap-preserving reduction from $L$ to the $(1-2\epsilon_0)$-GAP $q_0$CSP problem, and the PCP theorem is proved.


My questions:

First I will ask about what I think is an easy typo, and this question leads to my next question.

In the sentence beginning with "We get an instance $\psi\ldots",$ instead of $$\operatorname{val}(\psi) \leq 1 - \min\{2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0$$ Don't they instead mean $$\operatorname{val}(\psi) \leq \min\{1 - 2\epsilon_0, 1 - 2^{\log m}/m \} = 1 - 2\epsilon_0 ?$$

I am assuming (and tried to confirm) that their logarithm is base 2.

Second, I don't buy that $\operatorname{val}(\psi) \leq \min\{1 - 2\epsilon_0, 1 - 2^{\log m}/m \}.$ In particular, they say "apply the function $f$ obtained by Lemma 22.4 to $\varphi$ a total of $\log m$ times".

Shouldn't they instead say, "apply the function $f$ obtained by Lemma 22.4 to $\varphi$ up to a total $\log m$ times, until you get $\epsilon \geq \epsilon_0$."?

This is because applying Lemma 22.4 to $\varphi$ is only relevant if $\epsilon < \epsilon_0.$

Next, assuming the answer to my last question is "yes", then what if after applying the function $f$ zero or more times, we get an $\epsilon$ with $\epsilon = .51\epsilon_0$? In that case, when we apply $f$ once more, we amplify the gap to $2\epsilon = 1.02\epsilon_0$. In this case, we'd have $\operatorname{val}(\psi) \leq 1 - 1.02\epsilon_0$, in which case the lemma is no longer relevant. So I ask the next question:

Doesn't the previous paragraph suggest that we only get $\operatorname{val}(\psi) \leq 1 - \epsilon_0$?

If this is the case, then I believe we can finish their proof by correcting their last sentence so that it says this: "Thus we have obtained a gap-preserving reduction from $L$ to the $(1-\epsilon_0)$-GAP $q_0$CSP problem, and the PCP theorem is proved."

$\endgroup$
8
$\begingroup$

I think you're right about the first typo.

I think the authors are actually fine on the other two questions. Imagine you've applied $f$ exactly $\log_2 m$ times and that $\varphi$ was unsatisfiable. At some first time $k<\log_2 m$, you know $\text{val}(f^{(k)}(\varphi))\leq 1-\epsilon_0$ because you double the gap while the value is at least $1-\epsilon_0$ because of the Lemma, and certainly this can't happen $\log_2 m$ times. Applying the lemma once more, it is true that $\text{val}(f^{(k+1)}(\varphi))\leq 1-2\epsilon_0$, because even if the previous gap was much bigger than $\epsilon_0$, note that the Lemma does not say you double the true gap of $f^{(k)}(\varphi)$ by applying $f$ again. Rather, it says you can ensure the new gap is at least twice any lower bound on the current gap that is not more than $\epsilon_0$. Because $\epsilon_0$ is such a lower bound, you get the stated claim. This applies for $k+1,\ldots,\log_2 m$. In other words, you may or may not make any more progress by continuing to apply $f$, but you will be at most $1-2\epsilon_0$.

| cite | improve this answer | |
$\endgroup$

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.