I am thinking of the equality "PCP(O(log(n)),0) = P"

Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of this algorithm say $A_P$ such that it uses log(n) random bits. Now if I prove somekind of (exactly what ?) expectation correctness of $A_P$ then does it imply that $A$ was correct?

If the above is not right then I would like if someone can point me to what is the closest correct thing to this!


The statement you state is not the PCP theorem. The PCP theorem is a characterization of NP.

The statement you mention is much easier to prove. It says in effect that a polytime algorithm that uses $O(\log n)$ random bits can be made deterministic while keeping it polytime (given reasonable completeness and soundness properties). The proof is very simple – we can run the algorithm over the $2^{O(\log n)} = n^{O(1)}$ many choices of random bits, check how many times the algorithm accepts, and so determine whether the input belongs to the language.

At most you can think of this as a derandomization procedure – if your algorithm uses only logarithmically many random bits, then you can make it deterministic by "exhaustive search".

| cite | improve this answer | |
  • $\begingroup$ Yes. Thanks! Are there other polytime derandomizations possible? Like if there were linear number of coin tosses? $\endgroup$ – user6818 May 3 '15 at 22:41
  • $\begingroup$ It is suspected that P=BPP, that is, that we can deal with any polynomial number of coin tosses. But we don't know how to prove it right now. $\endgroup$ – Yuval Filmus May 3 '15 at 22:43
  • $\begingroup$ I understand that. But I hear of of this implicit idea which I am not able to trace an exact reference to learn from - that even within our current knowledge there are ways to convert a probabilistic algorithm proof into a proof for a deterministic one - under what conditions and how? (any pedagogic reference to read would be helpful!) [...I actually currently have at hand a deterministic polynomial algorithm which is doing something amazing but I don't know how to prove it directly and hence I am looking for this approach to a possible proof...] $\endgroup$ – user6818 May 4 '15 at 20:32
  • $\begingroup$ There is an entire area dealing with this problem, known as derandomization. $\endgroup$ – Yuval Filmus May 4 '15 at 21:04
  • $\begingroup$ :D Anything simple/pedagogic I can read off immediately to learn enough to try to use something in a special case? $\endgroup$ – user6818 May 4 '15 at 23:01

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.