patternModerate
Problems in P with provably faster randomized algorithms
Viewed 0 times
withrandomizedalgorithmsfasterproblemsprovably
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#2362, answer score: 17
Revisions (0)
No revisions yet.