Let's say I can solve problem $A$ in polynomial time using only $\log n$ bits of randomness, with a $\ge \frac{2}{3}$ chance of a correct answer. Then surely I can solve $A$ determistically by running my algorithm for $A$ over all random strings of length $\log n$ (of which there are a polynomial number) and take a popular vote of the outcomes.

I don't understand, then, why we would ever talk about $O(\log n)$ amounts of randomness in complexity classes that are closed under polynomial factors. More specifically, the PCP theorem says $NP = PCP[O(\log n), O(1)]$ - why isn't that the same as $PCP[0, O(1)]$?


We can! However, the PCP theorem does not say that we can solve the problem using $\log n$ bits of randomness. It says that we can verify a solution with $\log n$ bits.

Recall that a standard definition of NP is the class of languages for which there is a deterministic, polynomial-time verifier: For each $x$ in the language, there is a certificate $y$ so that the verifier accepts $\langle x,y \rangle$, and there is no such $y$ if $x$ is outside the language.

The PCP theorem says that we could also define NP as the class of languages for which there is a randomized, polynomial-time verifier that uses $\log n$ bits of randomness and reads only a constant number of bits of the certificate $y$.

Notice that if you derandomize the $\log n$ bits of randomness by enumerating them all and running this verifier on each one, you end up with a deterministic algorithm that will read the entire certificate $y$, which matches the standard definition of NP above.


The PCP theorem states that every NP problem has a polynomial size certificates (for the YES instances) that can be checked (up to a small constant error) by reading only constantly many bits of the proof. This does not give you an algorithm to solve the problem since guessing the certificate would take exponential time. On the other hand, the fact that the certificate is only polynomial size, and that the verification consists of reading only constantly many bits, puts this proof system in NP.


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.