Randomisierter Algorithmus zur Überprüfung der Erfüllbarkeit von S-Formulas, die die richtige Antwort mit einer Wahrscheinlichkeit mindestens $ frac {2} {3} $ ausgibt

Question

Ich versuche mich mit zufälligen Algorithmen zu üben.

Nennen wir eine CNF-Formel über n Variablen s-formul, wenn sie entweder nicht nachvollziehbar ist oder mindestens $ frac {2^n} {n^{10}} $ erfüllende Zuordnungen.

Ich möchte, dass Ihre Hilfe bei der Anzeige eines randomisierten Algorithmus zur Überprüfung der Erfüllbarkeit von S-Formulas die richtige Antwort mit einer Wahrscheinlichkeit von mindestens $ frac {2} {3} $ gibt.

Ich bin mir nicht sicher, wie ich es beweisen soll. Als erstes kommt mir das Ding- lassen Sie uns mit Wahrscheinlichkeit $ frac {2} {3} $ jede Eingabe $ akzeptieren. Wenn der Eingang in der Sprache dann angenommen wurde, ob im ersten Wurf ($ frac {2} {3} $) oder es nicht war und dann die Wahrscheinlichkeit zu akzeptieren, dass es $ frac {1} {3} ist CDOT -PROBALIBALE -TO -AKTE $, was größer ist als $ frac {2} {3} $. Ist dies der Weg, dies zu tun, oder sollte ich irgendwie Chernoff -Ungleichheit verwenden, was ich nicht sicher bin.

Answer 1

Grundidee: Wählen Sie eine zufällige Zuordnung aus und überprüfen Sie sie. Dann wiederholen Sie es viele Male. Auch wenn eine der Aufgaben die Formel erfüllt, die Sie "Ja" beantworten (ansonsten antworten Sie "Nein"))

Wir wissen, dass die Eingabeformel "einfach" ist: In einfachen Worten bedeutet dies, dass sie entweder nicht unzufrieden ist oder Es hat "viele" befriedigende Aufgaben. Wenn es nicht befriedigend ist - egal welche Aufgaben Sie auswählen, wird dies die Formel niemals erfüllen. Daher beantwortet der obige Algorithmus für solche Eingaben immer korrekt, und ab diesem Zeitpunkt und weiter berücksichtigen wir nur Befriedigung Eingaben.

Wie ist die Wahrscheinlichkeit, dass eine zufällige Zuordnung sie erfüllt?

Sei $ varphi $ ein cnf über $ n $ variablen mit mehr als $ 2^n/n^{10} $ erfüllende Zuordnungen, dann $$ pr_ {x sim u} [ varphi (x) = t] Ge Frac {2^n/n^{10}} {2^n} $$

Jetzt wiederholen wir es $ k $ mal (Sie müssen $ k $ sorgfältig auswählen. Lassen Sie es uns später tun). Jedes Mal, wenn wir ein zufälliges $ x $ auswählen. Sei $ e_i $ das Ereignis, das in der $ i $ -Tanz $ varphi $ erfüllt ist. Wie hoch ist die Wahrscheinlichkeit, dass wir nach einem Versuch von $ k $ mindestens eine zufriedenstellende Aufgabe herausfinden?

Es ist $ pr [ bigcup_ {i = 1}^k e_i] $. Wir wissen, dass $ pr [e_i] ge 1/n^{10} $, und Sie können die Standard -Linearität (von unabhängigen Ereignissen) verwenden, um es auszuarbeiten.

Letzter Schritt - Finden Sie das (minimale) $ k $, das $ pr [ cup_k e_i] ge 2/3 $ nach Bedarf macht.

Bonus-Frage: Wie niedrig können Sie $ k $ (und Ihren Algorithmus effizienter machen), wenn Sie die oben genannte mithilfe der Ungleichheit von Chernoff analysieren?

Answer 2

Ihr Vorschlag funktioniert nicht. Wenn die Formel nicht zufrieden ist, gibt Ihr Algorithmus die richtige Antwort mit nur 1/3 $ aus.

Hinweis: Wenn eine Formel $ 2^n/n^{10} $ erfüllt werden, wie hoch ist die Wahrscheinlichkeit, dass eine zufällige Zuordnung erfüllt ist?