JUCS - Journal of Universal Computer Science 12(6): 746-761, doi: 10.3217/jucs-012-06-0746
Randomized Algorithms and Complexity Theory
expand article infoHarald Hempel‡
‡ Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany

Corresponding author: Harald Hempel ( hempel@informatik.uni-jena.de )

© Harald Hempel.
This article is freely available under the J.UCS Open Content License.
Citation: Hempel H (2006) Randomized Algorithms and Complexity Theory. JUCS - Journal of Universal Computer Science 12(6): 746-761. https://doi.org/10.3217/jucs-012-06-0746
Open Access
Abstract
In this paper we give an introduction to the connection between complexity theory and the study of randomized algorithms. In particular, we will define and study probabilistic complexity classes, survey the basic results, and show how they relate to the notion of randomized algorithms.
Keywords
randomized algorithms, randomized complexity classes