patternMinor
On certificates in BPP (avoiding majority vote)
Viewed 0 times
majoritycertificatesbppvoteavoiding
Problem
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.
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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#54657, answer score: 3
Revisions (0)
No revisions yet.