I missed the lecture on randomised algorithms and can't wrap my head around amplifying the probability of a two sided error algorithm.
Can someone explain why the probability that the following algorithm gives a correct output increase through repetition and how can that probability be calculated?
L is a formal language
If the input x ∈ L, the output of the algorithm will be YES with a probability of 2/3
If the input x !∈ L, the output of the algorithm will be NO with a probability > 1/2
Thank you in advance
Aucun commentaire:
Enregistrer un commentaire