I am trying to proof the following statement:

If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$.

Here are my ideas for the proof: It can be easily worked from here that there exists an nondeterministic Turing machine $N$ solving any SAT instance in time $o(n^{q})$ for any $q \in R^{+}$. I believe it should lead to a contradiction somewhere (maybe alteration theorems). I had another approach to guess the certificate, but that takes time $2^{2^{o(\log n)}}$ which is not always polynomially bounded.

Source: PCP Course By Prahladh Harsha. This was one of the excercise questions. I am self studying this, so this does not violate any ethical arguments.


You can actually show a slightly stronger result: if $SAT \in PCP(o(\log n), o(\log n))$ then P=NP. The idea is to apply the implied reduction repeatedly, reducing the size of the instance all the way down to $O(\log n)$, at which point you can solve it by trying all certificates.

For more details, Arora and Safra (page 76) suggest looking at Theorem 26 in the appendix of FGLSS (journal version). Unfortunately, this appendix doesn't seem to be available any more.


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.