# Relationship between Las Vegas algorithms and deterministic algorithms

I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm:

Suppose that there is a Las Vegas algorithm $A$ that solves some graph problem $P$, i.e., $A$ takes an $n$-node input graph $G$ as input (I'm assuming the number of edges is $\le n$) and eventually yields a correct output, while terminating within time $T(G)$ with some nonzero probability.

Suppose that there is no deterministic algorithm that solves $P$. Let $A^\rho$ be the deterministic algorithm that is given by running the Las Vegas algorithm $A$ with a fixed bit string $\rho$ as its random string. Let $k=k(n)$ be the number of $n$-node input graphs (with $\le n$ edges). Since there is no deterministic algorithm for $P$, it follows that, for any $\rho$, the deterministic algorithm $A^\rho$ fails on at least one of the $k$ input graphs. Returning to the Las Vegas algorithm $A$, this means that $A$ has a probability of failure of $\ge 1/k$, a contradiction to $A$ being Las Vegas.

-
these are more typically called "Monte Carlo" algorithms. there is another way to study this problem. imagine that a Monte Carlo algorithm is combined with a PRNG, but that is equivalent to a deterministic algorithm. the actual problem/challenge here is called "derandomization" & is a complex topic in TCS.. still looking for good survey... – vzn Mar 10 '14 at 3:45
@vzn No. A Las Vegas algorithm is one that takes a random amount of time but always gives the right answer; a Monte Carlo algorithm takes a fixed amount of time but may give the wrong answer. – David Richerby Mar 10 '14 at 7:22
oops ok! las vegas algorithm wikipedia – vzn Mar 10 '14 at 15:14

There is no contradiction here. A Las Vegas algorithm terminates in expected polynomial time, say $Q(n)$. Markov's inequality shows that for any given polynomial $R(n)$, it terminates in polynomial time $Q(n)R(n)$ with probability $1-1/R(n)$. The number of graphs on $n$ vertices, $k(n)$, is exponential in $n$, so the failure probability $1/R(n)$ is much larger than $1/k(n)$.

Another subtle point is uniformity. A deterministic algorithm needs to handle any input size, while your $A^\rho$ can only handle inputs of certain size. In general, a randomized algorithm can use an unbounded number of random bits. However, your argument can still be formulated in terms of non-uniform models such as circuits, and it is still wrong for the reason described above.

-
OK, now I understand what you're saying. But I don't see why you're assuming that a Las Vegas algorithm must terminate in expected polytime. For example, isn't bogosort an Las Vegas algorithm running in something like factorial time? (Guaranteed to produce the right answer but running time is random.) – David Richerby Mar 10 '14 at 12:24
A "polynomial time Las Vegas algorithm" is a randomized algorithm whose expected running time is polynomial. It's true that every language computed in expected time $T(n)$, for any $T(n)$, is computable, since you can try all possible random strings in parallel. – Yuval Filmus Mar 10 '14 at 19:23
Sure. But this question is about Las Vegas algorithms in general, with no restriction to ones that run in expected polynomial time. – David Richerby Mar 10 '14 at 20:07

Your algorithm $A^\rho$ has a fixed string of "random" bits, of fixed length $|\rho|$. That means it can only simulate $A$ on inputs that require at most $|\rho|$ random bits to process. If that is all inputs, then you have your deterministic algorithm right there. Otherwise, $A^\rho$ is not a simulation of $A$ on all inputs, so it does not solve $P$, as it was claimed to.

-
As I comment in my answer, while this is one reason why the argument fails, it would fail even in the non-uniform model. – Yuval Filmus Mar 10 '14 at 12:03

There are several subtleties here.

1. The existence of a Las Vegas algorithm does imply the existence of a deterministic algorithm: Simply simulate the Las Vegas algorithm on all possible random strings, dovetailing the computation so that they are computed in parallel, until one of the computations return an answer. This doesn't necessarily mean that there is an efficient deterministic algorithm, however (e.g. one running not much slower than the expectation of the Las Vegas algorithm).

2. To produce a contradiction, you gave your deterministic algorithm oracle access to a single, fixed random string. This is "deterministic", since the string is fixed, but it is no longer a polynomial-time algorithm because it gets to read this fixed random string. This random string must grow with the size of the input, so essentially you've given your algorithm access to an infinite amount of information. This is what's referred to as a non-uniform model of computation -- the algorithm gets some amount of "advice" that is growing in the size of the input. So you would have shown that there is a non-uniform deterministic algorithm running in about the same time as the expected runtime of the algorithm. But you would not have shown that there is a uniform deterministic algorithm.

3. As Yuval points out in his first paragraph, it's ok that, for a fixed random string $\rho$, the algorithm returns "fail" with probability much greater than $1/k(n)$ (with $k(n)$ the number of $n$-node graphs). We just need something like, for each input graph, for "most" random strings $\rho$, we get back an answer.

-