Randomized Algorithms and Complexity Theory
Дата
Авторы
Hempel,Harald
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
randomized algorithms , randomized complexity classes