# Logarithmic Randomness is Necessary for PCP Theorem

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.