Derandomizing Valiant-Vazirani?

29

Das Valiant-Vazirani- Theorem besagt, dass, wenn es einen (deterministischen oder randomisierten) polynomiellen Zeitalgorithmus gibt, um zwischen einer SAT-Formel mit genau einer erfüllenden Zuordnung und einer nicht erfüllbaren Formel zu unterscheiden, NP = RP . Dieses Theorem wird bewiesen, indem gezeigt wird, dass UNIQUE-SAT unter randomisierten Reduktionen NP- hart ist .

Vorbehaltlich plausibler Derandomisierungsvermutungen kann der Satz gestärkt werden, um "eine effiziente Lösung für UNIQUE-SAT impliziert NP = P ".

Mein erster Instinkt war zu glauben, dass es eine deterministische Reduktion von 3SAT zu UNIQUE-SAT gibt, aber mir ist nicht klar, wie diese spezielle Reduktion derandomisiert werden kann.

Meine Frage ist: Was wird über "Derandomisierung von Reduktionen" geglaubt oder gewusst? Ist es / soll es möglich sein? Was ist mit VV?

Da UNIQUE-SAT für PromiseNP unter randomisierten Reduktionen vollständig ist , können wir mit einem Derandomisierungs-Tool zeigen, dass "eine deterministische polynomielle Zeitlösung für UNIQUE-SAT PromiseNP = PromiseP impliziert " ?

cc.complexity-theory reductions derandomization unique-solution Henry Yuen
quelle

4

Wie im letzten Absatz entspricht PromiseP = PromiseNP P = NP.

Tsuyoshi Ito

31

Unter den richtigen derandomization Annahmen (siehe Klivans-van Melkebeek ) Sie folgende erhalten: Es gibt eine polytime berechenbare st für alle , $f(\phi)=(\psi_1,\ldots,\psi_k)$ $\phi$

Wenn erfüllbar ist, hat mindestens einer der genau eine erfüllende Zuordnung. $\phi$ $\psi_i$
Ist nicht erfüllbar, sind alle nicht erfüllbar . $\phi$ $\psi_i$

Sie benötigen ein k-Polynom in der Länge von . Für wahrscheinlich nicht möglich . $\phi$ $k=1$

Lance Fortnow
quelle

@LanceFortnow impliziert dass das Vazirani-Valiant-Isolations-Lemma derandomisiert werden kann, und daher impliziert eine deterministische Reduktion auf die ?

P=BPP $P=BPP$

SAT $SAT$

P=NP $P=NP$

T ....

1

Nein. Sie benötigen eine stärkere Annahme als P = BPP, um Valiant-Vazirani zu derandomisieren (ich verweise Sie erneut auf Klivans-van Melkebeek). Selbst wenn Sie Valiant-Vaizarni derandomisieren, erhalten Sie nur das oben erwähnte Ergebnis - Sie würden P = NP erhalten, wenn Sie keinen Algorithmus hätten, der die Erfüllbarkeit mit eindeutigen Zeugen lösen könnte.

Lance Fortnow

@LanceFortnow Nur um klar zu sein. Können wir durch nur oder ist es wesentlich, dass (mit dem Wissensstand, den wir haben) es wahrscheinlich ist, dass wir VV derandomisieren müssen, um zu bekommen zu (dies ist eine etwas andere Abfrage als nur zu fragen, ob P = BPP eine deterministische Reduktion SAT ergibt, da es möglicherweise nicht wesentlich ist, dass VV überhaupt in der ersten benötigt wird platziere um NP in BPP zu bekommen ^ {oplus P}).

P⊕P=BPP⊕P $P^{\oplus P}=BPP^{\oplus P}$

P=BPP $P=BPP$

P⊕P=BPP⊕P $P^{\oplus P}=BPP^{\oplus P}$

T ....

22

Nur zum Nachschlagen bin ich heute auf dieses wirklich interessante Papier gestoßen, das beweist, dass eine deterministische Reduktion unwahrscheinlich ist:

Dell, H., Kabanets, V., Watanabe, O. & van Melkebeek, D. (2012). Ist das Valiant-Vazirani-Isolations-Lemma verbesserbar? ECCC TR11-151

Sie argumentieren, dass dies nur möglich ist, wenn NP in P / poly enthalten ist.

Henry Yuen
quelle

Derandomizing Valiant-Vazirani?

Antworten: