4
$\begingroup$

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output.

However if the problem $\Pi$ is also in $NP$ instead of running $A$ so many times why cant we after every run verify the certificate that $A$ produces is correct? If correct after a particular run and the answer is $Yes$ and the certificate is accepted then declare answer as $Yes$ else if the answer is $Yes$ and the certificate is not accepted then declare answer as $No$.

This should be much faster than taking majority vote.

$\endgroup$
  • 1
    $\begingroup$ By Corollary 4.8 ("There exists a relativized world where EXP$^{\hspace{.02 in}\text{NP}}$ is in BPP and ...") and "the hierarchy theorem for relativized Turing machines", no result along the lines of what you're trying can relativize. ​ ​ ​ ​ $\endgroup$ – user12859 Mar 19 '16 at 13:15
3
$\begingroup$

A randomized algorithm $A$ does not produce any sort of "certificate" in any useful sense. Even if $A$ is a correct BPP algorithm, all that you know by running $A$ once is that it gives this particular outcome on this particular set of coin tosses. How would you use this fact as a witness that the input is or is not in the language? A correct BPP algorithm may give the right or wrong answer on this particular run.

In contrast, a correct deterministic algorithm does give a certificate from only running it once because it will give the same (correct) answer every time. Whereas you would need to run $A$ on all possible coin tosses and concatenate these answers to get any sort of "proof" about the input.

Another approach to your question: you could also start from the fact that a problem is in NP and try to design a randomized algorithm that both solves it and produces witnesses when it does. Here, however, as Yuval says, the issue is that witnesses may be very unlikely to guess so we do not know how to do this in general. If we could show that a randomized polynomial-time algorithm can reliably guess witnesses when they exist, we will essentially have shown $NP \subseteq BPP$.

$\endgroup$
  • $\begingroup$ (Note that by search-to-decision for SAT, if $\: NP\subseteq BPP \:$ then $\: RP=NP \;$.) $\;\;\;\;$ $\endgroup$ – user12859 Mar 20 '16 at 10:29
1
$\begingroup$

The algorithms witnessing that $\Pi \in \mathsf{BPP}$ and that $\Pi \in \mathsf{NP}$ could be different. You cannot interpret random coin tosses used by $\mathsf{BPP}$ algorithms as witnesses for $\mathsf{NP}$ algorithms.

$\endgroup$
  • $\begingroup$ Assume we have $BPP$ algorithm $A$ and $NP$ algorithm $A'$. Each algorithm could produce a different short certificate for $Yes$ instances which can be checked in poly time correct? $\endgroup$ – user39969 Mar 19 '16 at 12:35
  • $\begingroup$ The successful witnesses for $A'$ could be rare. You cannot use the guarantee of the BPP algorithm for your NP algorithm. $\endgroup$ – Yuval Filmus Mar 19 '16 at 12:36
  • $\begingroup$ What do you mean by successful witnesses for $A'$ could be rare? $\endgroup$ – user39969 Mar 20 '16 at 0:09
  • 1
    $\begingroup$ Short, but not necessarily common. Give it a few hours. $\endgroup$ – Yuval Filmus Mar 20 '16 at 0:40
  • 1
    $\begingroup$ Nothing. That's the usual case for hard instances. $\endgroup$ – Yuval Filmus Mar 20 '16 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy