I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem".

The results of these sections show that $NP \subset OPT (poly(n), 1)$ (Theorem 5) and $NP \subset OPT (\log n, poly \log n)$ (Theorem 8). Theorems 9 and 10 show that the recursion idea applies to these proof systems, and in particular shows the following:

  1. $OPT (f (n), g(n)) \subset OPT (f (n) + O(\log g(n)), (\log g(n))^{O(1)} )$ and
  2. $OPT (f (n), g(n)) \subset OPT (f (n) + (g(n))^{O(1)} , 1)$.

This allows us to conclude that $NP \subset OPT (\log n, poly \log \log n)$ (by composing two $OPT (\log n, poly \log n)$ proof systems) and then by composing this system with the $OPT (poly(n), 1)$ proof system we obtain $OPT (\log n, 1)$ proof system for $NP$.

Edit. Composition of verifiers is defined in Probabilistic Checking of Proofs: A New Characterization of NP section 3 (page 13) "Normal Form Verifiers and Their Use in Composition".

Let $r, q, s, t$ be any functions defined on the natural integers. Suppose there is a normal-form verifier $V_2$ that is $(r(n), s(n), q(n), t(n))$-constrained. Then, for all functions $R, Q, S, T$, $$RPCP(R(n), S(n), Q(n), T(n)) \subseteq \\RPCP(R(n) + r(\tau), s(\tau), Q(n) + q(\tau), Q(n)t(\tau))$$ where $\tau$ is a shorthand for $O((T(n))^2)$.

Where $RPCP(r, s, q, t)$ is a $PCP(r, s \cdot q)$ which takes $t$ time to accept of reject after reading the $s \cdot q$ bits.

I still don't see how this composition works. Is $OPT(r, q) = RPCP(r, q, 1, q)$ and a normal form verifier? In that case it seems to work, but then just composing $OPT(poly(n), 1)$ with $OPT(\log n, poly \log n)$ is enough, so why bother with $OPT(\log n, poly \log \log n)$ or relations $1.$ and $2.$?

  • 2
    $\begingroup$ Did you check the references given in 1.2, in particular [AS92]? $\endgroup$ – Raphael Mar 15 '14 at 11:28
  • 2
    $\begingroup$ Check Arora's thesis, Lemma 3.1 on page 20. (Link: cs.princeton.edu/~arora/pubs/thesis.pdf) $\endgroup$ – Yuval Filmus Mar 15 '14 at 12:30
  • $\begingroup$ Did you find your answer in these references? $\endgroup$ – Raphael May 7 '14 at 14:04
  • $\begingroup$ @Raphael, partly. I added a more specific question with an edit. $\endgroup$ – Karolis Juodelė May 7 '14 at 14:10
  • $\begingroup$ @YuvalFilmus Did you see the updated question? $\endgroup$ – Raphael Dec 6 '14 at 9:30

Your Answer

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

Browse other questions tagged or ask your own question.