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

cs.stackexchange https://cs.stackexchange.com/questions/23104

  •  31-10-2019
  •  | 
  •  

Pergunta

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

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top