Randomisierter Algorithmus für 3SAT

8

Es gibt einen sehr einfachen randomisierten Algorithmus, der bei einem 3SAT eine Zuordnung erzeugt, die mindestens 7/8 der Klauseln erfüllt (in Erwartung): Wählen Sie eine zufällige Zuordnung. Eine zufällige Zuordnung erfüllt jede Klausel mit einer Wahrscheinlichkeit von 7/8, und die Linearität der Erwartung zeigt, dass der erwartete Anteil der Klauseln, die durch eine zufällige Zuordnung erfüllt werden, 7/8 beträgt.

Kann dies deterministisch erfolgen? Wenn ja, warum interessieren wir uns für den randomisierten Algorithmus?

Yuval Filmus
quelle

Antworten:

6

Der Zufallszuweisungsalgorithmus kann unter Verwendung der Methode der bedingten Erwartungen derandomisiert (deterministisch gemacht) werden.

Die 3SAT-Instanz bestehe aus den Klauseln C1,,Cm . Während des Algorithmus weisen wir Variablen Werte zu. Die Punktzahl einer Klausel C. ist wie folgt definiert:

  • Wenn C. erfüllt ist, ist seine Punktzahl 1.
  • Wenn C. nicht zufrieden ist und k nicht zugewiesene Literale hat, beträgt seine Punktzahl 12k .

Zunächst wird die Punktzahl jeder Klausel 1- -2- -3=7/.8 , und so die Gesamtpunktzahl ist (7/.8)m . Wir weisen nun den Variablen x1,,xn Reihe nach Werte zu . Angenommen, wir haben den Variablen x1,,xich- -1 Werte zugewiesen , und die aktuelle Gesamtpunktzahl ist S.=S.(C.1)++S.(C.m) . SeiS0,S1 die Gesamtpunktzahl, wenn wir x i die Werte0,1 (jeweils)zuweisen. Ich beanspruchedass S 0 ( C ) + S 1 ( C ) = 2 S ( C ) für jede Klausel C , und so S 0 + S 1 = 2 S . Tatsächlich:xiS0(C)+S1(C)=2S(C)CS0+S1=2S

  • Wenn C erfüllt ist (nur x1,,xi1 ) oder xi nicht enthält, dann ist S0(C)+S1(C)=2S(C) .
  • Angenommen, C enthält k nicht zugewiesene Literale, einschließlich xi . Dann ist S(C)=12k , S0(C)=12(k1) und S1(C)=1 . Daher ist
    S0(C)+S1(C)=[122k]+1=2(12k)=2S(C).
  • Ein ähnliches Argument funktioniert, wenn Cx¯i enthält .

Da S0+S1=2S , ist entweder S0S oder S1S (möglicherweise beides). Daher gibt es eine Zuordnung zu S so dass nach der Zuweisung die neue Punktzahl mindestens S beträgt .

Der Anfangsstand (7/8)m , und der Algorithmus sicher , dass die Kerbe nicht abnimmt. Am Ende ist die Punktzahl einer Klausel C 1, wenn sie erfüllt ist, und andernfalls 120=0 . Somit wird die endgültige Zuordnung erfüllt mindestens (7/8)m - Klauseln.

Warum interessieren wir uns angesichts des deterministischen Algorithmus für den randomisierten? Es gibt verschiedene Gründe:

  1. Der randomisierte Algorithmus ist viel einfacher.
  2. Der randomisierte Algorithmus ist möglicherweise schneller.
  3. Der randomisierte Algorithmus kann unter Verwendung der Methode der bedingten Erwartungen in einen deterministischen Algorithmus umgewandelt werden. wir können es uns als ein Rezept für die Konstruktion eines deterministischen Algorithmus vorstellen.

P=BPP

Yuval Filmus
quelle