Go home now Header Background Image
Search
Submission Procedure
share: |
 
Follow us
 
 
 
 
Volume 12 / Issue 6

available in:   PDF (151 kB) PS (136 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
Links into Future
 
DOI:   10.3217/jucs-012-06-0746

 

Randomized Algorithms and Complexity Theory

Harald Hempel (Friedrich-Schiller-Universit├Ąt Jena, Germany)

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

Categories: F.1.2, F.1.3, F.2.2, F.2.3