2008 | OriginalPaper | Buchkapitel
Randomisierte Algorithmen und Komplexitätsklassen
Erschienen in: Komplexitätstheorie und Kryptologie
Verlag: Springer Berlin Heidelberg
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
Dieses Kapitel behandelt randomisierte Algorithmen und die entsprechenden probabilistischen Komplexitätsklassen. Randomisierte Algorithmen sind oft effizienter als die besten bekannten deterministischen Algorithmen für dasselbe Problem, zahlen dafür jedoch den Preis, Fehler zu machen. Dies ist das Thema in Abschnitt 6.1, in dem ausgewählte deterministische und randomisierte Exponentialzeit-Algorithmen für das Erfüllbarkeitsproblem vorgestellt werden.