Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
10. Probabilistic Complexity Classes
verfasst von : Steven Homer, Alan L. Selman
Erschienen in: Computability and Complexity Theory
Verlag: Springer US
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this chapter we study the benefits of adding randomness to computations. We treat randomness as a resource. Probabilistic algorithms allow computations to depend on the outcomes of an ideal random generator (i.e., on unbiased coin tosses). They can be classified by classifying the languages they are defined to accept. Important computational problems that seem to be infeasible by ordinary deterministic computations have efficient solutions using probabilistic algorithms. Such algorithms can be easily implemented, and fast and reliable solutions to otherwise difficult problems are then possible. There is a cost to this added efficiency, however, in that probabilistic algorithms do sometimes make errors.