Let\'s say I can solve problem $A$ in polynomial time using only $\\log n$ bits

Question

Let's say I can solve problem $A$ in polynomial time using only $log n$ bits of randomness, with a $ge rac{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)]$?

Explanation / Answer

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 angle$, 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.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.