1
$\begingroup$

Let's say that I have a Las Vegas algorithm for a given problem (whose answer is true/false for simplicity) with a chance of answering p, and a Montecarlo algorithm for the same problem which is q-correct (it gives the correct answer with a probability of at least q)

Could there be any way to combine them both in order to improve the overall chance of finding the correct answer? This could be running them in turns, or repeating any given algorithm for k times and then the other one

SO far, I thought of doing the following:

  1. Call the Las Vegas algorithm k times
  2. If it hasn't given an answer, run the MonteCarlo algorithm k' times so that, at least, the chance of the given answer being wrong is less than the chance the Las Vegas algorithm has for not answering at all

Could there be any other way to improve the success chance?

I have tried finding any case where this has been done, but apart from converting one kind of algorithm into the other, I haven't found much.

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "a Las Vegas algorithm with a chance of answering $p$"? By definition, a Las Vegas algorithm always answer the correct answer (but its computation time may vary). Do you mean that it has a probability $p$ of answering under a certain threshold time? $\endgroup$
    – Nathaniel
    Commented Nov 13, 2022 at 22:23
  • $\begingroup$ @Nathaniel By that I mean the chance it has to give an answer on a single run, without any kind of repetition of the algorithm if it "opts" not to answer $\endgroup$
    – Lightsong
    Commented Nov 13, 2022 at 23:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.