Unter Zuhilfenahme des Zufalls können sehr viele Berechnungen deutlich beschleunigt werden. So sind effiziente randomisierte Lösungen bekannt für Probleme, für die bisher unbekannt ist, ob sie (deterministisch) effiziente gelöst werden können.