Every randomized algorithm can be simulated by a deterministic algorithm, at the expense of an exponential increase in running time. Derandomization is about converting randomized algorithms into efficient deterministic algorithms.
Stats
|
created |
9 years, 5 months ago |
|
viewed |
25 times |
|
editors |
0 |
Top Answerers
more »
Recent Hot Answers
Efficient and simple randomized algorithms where determinism is difficultWhy does randomness have stronger effect on reductions than on algorithms?
Running a BPP algorithm with a half-random, half-adversarial string
Derandomizing Valiant-Vazirani?
Examples of successful derandomization from BPP to P
more »
