Zweck der Randomisierung / derandomisierung in grundsätzlich randomisierter Algorithmus für max;

Question

in den Abschnitten 5.1 von das Design von Annäherungsalgorithmen von Williamson und Shmoys, sie beschreiben a Basic Randomisierter Algorithmus für Max SAT und derAndomisieren Sie es. Der Algorithmus ist nur, um jede Variable 1 (true) mit der Wahrscheinlichkeit 1/2 und 0 (FALSE) mit der Wahrscheinlichkeit 1/2 zuzuordnen. Mit anderen Worten, probieren Sie regelmäßig aus dem Raum aller Lösungen gleichmäßig. Sie zeigen, dass dies eine 1/2-Näherung ist.

Dann beschreiben sie in Abschnitt 5.2, wie Sie ihn mit der Methode der bedingten Erwartungen unterirrieren. (Ich werde den Prozess hier nicht beschreiben, weil es nicht sehr komplex und weithin bekannt ist, ich gehe davon aus.)

meine Frage ist, warum die Mühe der Mühe der Erandomizierung auf diesen Weg? Oder sogar, warum machen Sie die Mühe, den Algorithmus in erster Linie zufällig zu machen?

es scheint mir, dass ein ebenso guter Algorithmus der einzige Liner sein würde, der deterministisch alle Variablen auf 1 festlegte, die ein paar Max SAT-Instanz als Input enthält, scheint mir, dass Sie dies auch erwarten würden (dh "in Erwartung würde es ") die Hälfte der Klauseln zufrieden stellen. Für mich scheint die Analyse des zufälligen Algorithmus wirklich zu sagen, dass jede feste Vermutung "gut" ist. (Anstatt zu zeigen, dass unser zufälliger Algorithmus inhärent gut ist.) Warum sollten Sie den Prozess des Randomisierungs- und derandomizing an erster Stelle durchlaufen?

Vielen Dank im Voraus!

Answer 1

Der Unterschied besteht darin, dass der randomisierte Algorithmus eine erwartete 1/2-Näherung an jedem Eingang garantiert. Im Gegensatz dazu ist es einfach, einen Gegner, einen Eingang zu erstellen (d. H. Eine Instanz von max-sat), für die der deterministische "Alle Variablen auf den wahren" Algorithmus null Klauseln zufrieden ist.

Denken Sie daran, dass der Probenraum für einen randomisierten Algorithmus über einen Satz von Hilfs-Zufallsbits ist. Es wird keine Wahrscheinlichkeitsverteilung über die -Angaben angenommen. Das typische Ziel des randomisierten Algorithmus-Designs ist für jeden Eingang, der in Erwartung gut gehandhabt wird. (Analyse von Algorithmus-Verhalten über eine angenommene Eingabeverteilung wird als durchschnittliche Fallanalyse ) bezeichnet.)

Was sind ein Zufallsbits von Hilfsmitteln?

Angenommen, wir haben eine randomisierte Turnierungsmaschine $ M_1 $ , die auf Instanzen von Länge $ N $ ausgeführt wird für nicht mehr als $ t (n) $ Zeit, während der es nicht mehr als $ R (n) \ le macht T (n) $ zufällige Entscheidungen. Wir können diese Maschine in eine deterministische Turing-Maschine $ M_2 $ mit zwei Eingangsbändern eingeben: Das übliche Band, das die Eingabezeichenfolge $ x $ von länge $ n $ , und ein Band, das einen String $ R $ der Länge $ r (n) $ . Die Zeichenfolge $ R $ ist unsere Saite von -Hilfs-Zufallsbits ; Es bestimmt, welche "zufälligen" Entscheidungen die Turingmaschine machen soll. Wenn wir sagen, dass der randomisierte Turing-Maschine $ M_1 (x) $ mit der Wahrscheinlichkeit übernimmt $ P $ , Dies entspricht dem Set, das Set zu sagen $$ A (x)=Links \ {R \ | \ R \ in \ {0, 1 \} ^ {r (| x |)}, m_2 (x, r ) \ text {akzeptiert} \ richtig \} $$ von $ R $ Zeichenfolgen, die $ M_2 (X, R) $ akzeptieren, bildet eine Fraktion $ p= | A (x) | / 2 ^ {| x |} $ des Satzes aller $ R $ Saiten.

Sie können erkennen, was hier los ist, wenn Sie die analoge Konstruktion für nichtdeterministische Turing-Maschinen gesehen haben. Wir können an eine NP-Maschine als nichtdeterministische Maschine denken, die exponentiell viele Kopien von sich verzweigt. Wir können es aber auch als deterministische -E-Verifizierer -Maschine vorstellen, die sowohl eine Eingabe als auch einen "-Schicht" erfordert, wobei die Annahmekriterien, die eine Eingabezeichenfolge in der Sprache in der Sprache befindet, in der Sprache, wenn beliebige Resische Zeichenfolge macht die Maschine akzeptiert.

Es ist oft einfacher, über dieses bodenständige Konzept von deterministischen Verifiermaschinen nachzudenken, und welche Untermenge von Beweiszeichenfolgen die Maschine an einem bestimmten Input akzeptieren, anstatt an sehr abstrakte Ideen wie exponentiell verzweigte Maschinen und mögliche Welten zu denken . Und es macht es einfacher, Komplexitätsklassen wie CO-NP, PP, BPP, ⊕P usw. zu definieren, die alle im Wesentlichen "NP mit einer anderen Annahmeregel" sind. Zum Beispiel:

• np ist die Set von Sprachen $ L $ , für die ein Polynom-Time-Verifier-Maschine vorhanden ist $ M_2 $ < / span> so, dass $ x \ in L $ , wenn und nur, wenn es einen $ r $ string gibt so dass $ M_2 (X, R) $ akzeptiert (wo die Länge der $ R $ Saite ist Begrenzt von einem Polynom $ R (| x |) $ ).
• bpp ist die Set von Sprachen $ L $ , für die ein Polynom-Zeit-Verifier-Maschinen-Maschine vorhanden ist $ m_2 (x , r) $ so, dass $ X \ in L $ impliziert, dass $ M_2 (X, R) $ akzeptiert für mindestens ⅔ von $ R $ Saiten und $ X \ NOTIN L $ impliziert dieser $ m_2 (x, r) $ akzeptiert höchstens ⅓ von $ r $ Saiten (wo der Länge der $ R $ Saiten werden von einem Polynom $ R (| x |) $ ) begrenzt.

Hinweis: Es ist meistens egal, ob wir den $ R $ Zeichenfolgen benötigen, um Länge genau $ r (n) $ oder höchstens $ r (n) $ , da es nur kürzere Zeichenfolgen erlaubt Erhöht die Anzahl der möglichen Saiten um einen konstanten Faktor.