Cheap and Secure Web Hosting Provider : See Now

[Answers] Why can't we derandomize the PCP theorem by iterating over all possible $\log n$ random strings?

, , No Comments
Problem Detail: 

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)]$?

Asked By : GMB

Answered By : usul

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback