1
$\begingroup$

Does every randomised algorithm have a corresponding deterministic algorithm solving the same problem?

I'm going to guess that the deterministic algorithm will take more time, while the randomised algorithm although it has errors will generally be faster. This is from what I have seen of them so far. Let me know if this is wrong.

$\endgroup$
2
$\begingroup$

If the running time of the algorithm is bounded, in the sense that for every input $x$ there is a number $T(x)$ such that whatever the coin tosses are, the algorithm always terminates within $T(x)$ steps, then you can always "try all possibilities" and convert your randomized algorithm to a deterministic one, albeit with a possibly much larger running time.

For polynomial time algorithms in particular, it is conjectured that you can derandomize any algorithm with at most a polynomial blow-up in time, a conjecture usually stated as $\mathsf{P}=\mathsf{BPP}$.

$\endgroup$

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.