This article surveys situations in which probabilistic algorithms offer speedup over what is possible using deterministic algorithms, either in practice or in principle.
Publié le : 1993-02-14
Classification:
Communication complexity,
integer factorization,
primality testing,
probabilistic complexity classes
@article{1177011079,
author = {Feigenbaum, Joan and Lagarias, Jeffrey C.},
title = {Probabilistic Algorithms for Speedup},
journal = {Statist. Sci.},
volume = {8},
number = {4},
year = {1993},
pages = { 20-25},
language = {en},
url = {http://dml.mathdoc.fr/item/1177011079}
}
Feigenbaum, Joan; Lagarias, Jeffrey C. Probabilistic Algorithms for Speedup. Statist. Sci., Tome 8 (1993) no. 4, pp. 20-25. http://gdmltest.u-ga.fr/item/1177011079/