Ist ein randomisierter Algorithmus eine Wahrscheinlichkeitsverteilung über den Satz von deterministischen Algorithmen?

Question

Wenn es einen endlichen Satz von Instanzen der Größe n und den Satz von (angemessenen) deterministischen Algorithmen gibt, ist der finiten.

Kann ein randomisierter Algorithmus als Wahrscheinlichkeitsverteilung über den Satz von deterministischen Algorithmen angesehen werden?Und wenn ja, warum?

Answer 1

Sie können an einen randomisierten Algorithmus als Zugriff auf eine zufällige Variable $ \ Mathbf {R} $ , die seine zufälligen Entscheidungen informiert.Für jede Fixierung von $ \ mathbf {r} $ erhalten Sie einen deterministischen Algorithmus, und auf diese Weise können Sie den ursprünglich randomisierten Algorithmus als Verteilung über deterministische Algorithmen anzeigen.

Betrachten Sie als Beispiel den randomisierten Algorithmus, um max-3sat zu lösen.Der Algorithmus wählt eine zufällige Aufgabe aus.Sie können an diese Zuweisung nachdenken, wie sie von $ \ Mathbf {R} $ angegeben ist.Jede bestimmte Aufgabe entspricht einem deterministischen Algorithmus, und der ursprünglich randomisierte Algorithmus ist nur die gleichmäßige Verteilung über diesen deterministischen Algorithmen.