19
$\begingroup$

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$? Here $\mathsf{PTIME}(f(n))$ means the set of languages decidable by a randomized TM with constant-bounded (one or two-sided) error in $f(n)$ steps.

Does randomness buy us anything inside $\mathsf{P}$?

To be clear, I am looking for something where the difference is asymptotic (preferably polynomial, but I would settle for polylogarithmic), not just a constant.

I am looking for algorithms asymptotically better in the worst case. Algorithms with better expected complexity are not what I am looking for. I mean randomized algorithms as in RP or BPP not ZPP.

$\endgroup$
  • $\begingroup$ Maybe "Yao's technique" is what you are looking for. A brief description can be found at cs.pitt.edu/~kirk/cs2150/yao/yao.html $\endgroup$ – Wu Yin Jun 13 '12 at 16:36
  • $\begingroup$ @WuYin if I understand correctly that goes in the direction of lower-bounding randomized algorithms by the average case behavior of deterministic algorithm.. I will look more into it, but the way I see it, this could only ever lead to proving that randomness does not buy us anything inside $P$.. Am I correct? $\endgroup$ – aelguindy Jun 13 '12 at 16:53
  • 1
    $\begingroup$ For finding any element in sequence of length $n$ with rank in [$\frac{n}{4}$,$\frac{3*n}{4}$] we can simply return any random element and it will be correct with $\frac{1}{2}$ probability hence its O(1)! Whereas a Deterministic algorithm would at least examine some fraction of the input and hence $\Omega(n)$. $\endgroup$ – rizwanhudda Jun 14 '12 at 1:55
  • $\begingroup$ @rizwanhudda There might be some problems with that. First, I am looking for a decision problem. Second, in the Turing model, returning a random element is $\Omega (n)$, since there is no random access. Maybe, the machine always outputs the first element? Still, the first problem is bigger. $\endgroup$ – aelguindy Jun 14 '12 at 8:49
  • 2
    $\begingroup$ The last paragraph does not make sense because every Las Vegas algorithm can be converted to a Monte Carlo algorithm. $\endgroup$ – Tsuyoshi Ito Jun 17 '12 at 13:32
17
$\begingroup$

Polynomial identity testing admits a randomised polynomial time algorithm (see the Schwartz-Zippel lemma), and we currently don't have a deterministic polynomial time or even a sub-exponential time algorithm for it.

Game tree evaluation Consider a complete binary tree with $n$ leaf nodes each storing a 0/1 value. The internal nodes contain OR/AND gates in alternate levels. It can be proved using adversary argument that every deterministic algorithm would have to examine $\Omega{(n)}$ leaf nodes in the worst case. However there is a simple randomised algorithm which takes has expected running time of $O(n^{0.793})$ Look at slides 14-27 of the talk.

Oblivious routing on a hypercube Consider a cube in $n$-dimensions containing $N=2^n$ vertices. Each vertex has a packet of data and a destination that it wants to eventually deliver the packet to. The destination of all the packets are different. Even for this, It has been proved that any deterministic routing strategy would take $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ steps. However, there is a simple randomised strategy which will finish in expected $O(n)$ steps with high probability.

Note that in randomised algorithms, the expected cost $E(F(n))$ with high probability (like for eg. $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$) is equivalent to worst case in practice.

$\endgroup$
  • $\begingroup$ Also, consider testing for matrices $A$, $B$ and $C$ if $A B = C$. We currently know no $o(2^{2.3})$ algorithm, we know a randomized $O(n^2)$ algorithm. The point is, are there problems for which we can prove that randomized algorithms are better? $\endgroup$ – aelguindy Jun 13 '12 at 16:48
  • $\begingroup$ @aelguindy I get your point. But, for PIT the best known determinstic algorithm is exponential. And, derandomizing PIT is an important open problem in Theoretical CS. $\endgroup$ – rizwanhudda Jun 13 '12 at 17:27
  • $\begingroup$ I have added Game tree evaluation and hypercube routing to the post, for which randomised algorithms do provably better than determinstic counterparts. $\endgroup$ – rizwanhudda Jun 13 '12 at 17:28
  • $\begingroup$ OK, for the Game Tree evaluation, if I understand correctly, it runs in expected $O(n^{0.793})$, right? I mean there are cases where it will run in $\Omega(n)$. Is it the case with the third example too? I am not allowing for better expected time, I am looking for better worst-case complexity, allowed error in the output. $\endgroup$ – aelguindy Jun 13 '12 at 21:39
  • 1
    $\begingroup$ So they are not better in worst case. As much as I appreciate the examples, I'm afraid that is not exactly what I am looking for. The examples were very enlightening though! $\endgroup$ – aelguindy Jun 13 '12 at 22:30
5
$\begingroup$

Investigating the worst-case is meaningless for randomised algorithms. Not only will the worst-case runtime often be infinite but also they can not outperform deterministic algorithms in that metric.

Consider any randomised algorithm $A$. Obtain a deterministic algorithm $B$ by fixing the random tape for $A$ to $0^\infty$. Then, $T_B(n) \leq T_A(n)$ for all $n$.

$\endgroup$
5
$\begingroup$

There are many problems where we know of an efficient randomized algorithm, and we don't know of any deterministic algorithm that we can prove is efficient. However, this may reflect shortcomings in our ability to prove things about complexity rather than any fundamental difference.

Based on your comment, it appears you meant to ask whether there exists any problem where there is an efficient randomized algorithm, and we can prove there is no deterministic algorithm of comparable efficiency. I don't know of any such problem.

Indeed, there are reasonable grounds to suspect that such problems might be unlikely to exist. Heuristically, the existence of such a problem would likely mean that secure cryptography is impossible. That seems like a rather implausible outcome.

What's the connection, you ask? Well, consider any randomized algorithm $A$ that solves some problem efficiently. It relies upon random coins: random bits obtained from a true-random source. Now suppose we take a cryptographic-quality pseudorandom generator, and replace the true-random source with the output of the pseudorandom generator. Call the resulting algorithm $A'$. Note that $A'$ is a deterministic algorithm and its running time is approximately the same as $A$.

Also, if the cryptographic PRNG is secure, heuristically we should expect $A'$ to be a good algorithm if $A$ is:

  • For instance, if $A$ is a Las Vegas algorithm (it always outputs the correct answer, and terminates rapidly with high probability), then $A'$ will be a pretty good deterministic algorithm (always outputs the correct answer, and terminates rapidly for most inputs).

  • As another example, if $A'$ is a Monte Carlo algorithm (deterministic running time, and outputs the correct answer with probability at least $1-\varepsilon$), then $A$ will be a pretty good deterministic algorithm (deterministic running time, and outputs the correct answer on a fraction $1-\varepsilon$ of all inputs).

Therefore, if the cryptographic PRNG is secure and there is an efficient randomized algorithm, you get a deterministic algorithm that is pretty good. Now there are many constructions of cryptographic PRNGs that are guaranteed to be secure if certain cryptographic assumptions hold. In practice, those cryptographic assumptions are widely believed: at least, secure commerce and transactions rely upon them being true, so we're apparently willing to bet large sums of money that secure cryptography exists. The only way this transformation can fail is if cryptographic PRNG don't exist, which in turn implies secure cryptography is impossible. While we don't have any proof that this isn't the case, it seems like an unlikely outcome.

Details of the construction: Here's how $A'$ works. On input $x$, it derives a seed for the cryptographic PRNG as a function of $x$ (e.g., by hashing $x$), and then simulates $A(x)$, using the output of the cryptographic PRNG as the coins for $A$. For instance, a specific instantiation would be to set $k=\text{SHA256}(x)$, then use $k$ as the seed for AES256 in counter mode, or some other cryptographic PRNG. We can prove the above statements under the random oracle model.

If you're unhappy with the idea that $A'$ might output incorrect results on some small fraction of inputs, that can be addressed. If you repeat $A'$ multiple times and take a majority vote, the error probability decreases exponentially fast in the number of iterations. So, by iterating a constant number of times, you can get the error probability $\varepsilon$ to be below $1/2^{256}$, which means the chances that you run across an input $x$ where the algorithm outputs the wrong answer are vanishingly small (less than the chances of getting struck by lightning multiple times in a row). Moreover, with the construction I gave above, the chances that an adversary can even find an input $x$ where $A'$ gives the wrong answer can be made very small, as that would require breaking the security of the SHA256 hash. (Technically, this requires the random oracle model to justify, so it means that $A$ must be chosen to be "independent" of SHA256 and not hardcode in it calculations that are related to SHA256, but almost all real-world algorithms will satisfy that requirement.)

If you want a stronger theoretical basis, you can iterate $A$ $\Theta(n)$ times, and get the error probability to be below $1/2^n$, where $n$ is the length of the input $x$. Now the fraction of $n$-bit inputs where $A'$ gives an incorrect answer is strictly less than $1/2^n$. But there are only $2^n$ possible $n$-bit inputs, and on each one $A$ is either correct or incorrect, so it follows that there is no input where $A'$ is incorrect: $A'$ is correct on all inputs, and this holds unconditionally. If $A$ runs in time $t(n)$, then $A'$ runs in time $\Theta(n \cdot t(n))$, so $A'$ is a bit slower than $A$ but not too much slower. This is the content of Adleman's proof that BPP is contained in P/poly. For practical purposes this is probably overkill, but if you like clean proofs that avoid cryptographic assumptions or if you approach this from a theoretician's perspective then you might like this version better.

For more details on the latter theoretical considerations and additional problems where we know of an efficient randomized algorithm but we don't know of any deterministic algorithm that we can prove is efficient, see https://cstheory.stackexchange.com/q/31195/5038

In summary: For any problem where we know an efficient randomized algorithm, we also know of a deterministic algorithm that seems likely to be efficient in practice -- but at present we don't know how to prove that it is efficient. One possible interpretation is that we're just not very good at proving stuff about algorithms.

$\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.