109

urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891

JUCS - Journal of Universal Computer Science

jucs

0948-695X 0948-6968

Journal of Universal Computer Science

10.3217/jucs-012-06-0746

28629

Research Article

F.1.2 - Modes of Computation F.1.3 - Complexity Measures and Classes F.2.2 - Nonnumerical Algorithms and Problems F.2.3 - Tradeoffs between Complexity Measures

Randomized Algorithms and Complexity Theory

Hempel

Harald

hempel@informatik.uni-jena.de 1

Institut für Informatik, Friedrich-Schiller-Universität Jena, , Germany

Institut für Informatik, Friedrich-Schiller-Universität Jena Germany

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

Academic editor:

2006

28 06 2006

12 6 746 761 9E06C7C4-7AC4-5422-A1F3-72FF54EF7999 6997044

Harald Hempel

This article is freely available under the J.UCS Open Content License.

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.