Dérandomiser Valiant-Vazirani?

29

Le théorème de Valiant-Vazirani dit que s'il existe un algorithme polynomial de temps (déterministe ou aléatoire) pour distinguer entre une formule SAT qui a exactement une affectation satisfaisante et une formule insatisfaisante - alors NP = RP . Ce théorème est prouvé en montrant que UNIQUE-SAT est NP- dur sous des réductions aléatoires .

Sous réserve de conjectures de dérandomisation plausibles, le théorème peut être renforcé pour "une solution efficace à UNIQUE-SAT implique NP = P ".

Mon premier réflexe a été de penser que cela impliquait une réduction déterministe de 3SAT à UNIQUE-SAT, mais je ne vois pas comment cette réduction peut être dérandomisée.

Ma question est: que pense-t-on ou sait-on des "réductions dérandomisantes"? Est-ce / devrait-il être possible? Et dans le cas de VV?

Puisque UNIQUE-SAT est complet pour PromiseNP sous des réductions aléatoires, pouvons-nous utiliser un outil de dérandomisation pour montrer qu '"une solution temporelle polynomiale déterministe à UNIQUE-SAT implique que PromiseNP = PromiseP ?

cc.complexity-theory reductions derandomization unique-solution Henry Yuen
la source

4

Comme pour le dernier paragraphe, PromiseP = PromiseNP est équivalent à P = NP.

Tsuyoshi Ito

31

Sous les bonnes hypothèses de dérandomisation (voir Klivans-van Melkebeek ), vous obtenez ce qui suit: Il y a un polytime calculable st pour tout , $f(\phi)=(\psi_1,\ldots,\psi_k)$ $\phi$

$\phi$ $\psi_i$
$\phi$ $\psi_i$

$\phi$ $k=1$

Lance Fortnow
la source

P = B P P

$P=BPP$

P = B P P

$P=BPP$

S A T

$SAT$

P = N P

$P=NP$

1

Non. Vous avez besoin d'une hypothèse plus forte que P = BPP pour dérandomiser Valiant-Vazirani (encore une fois, je vous renvoie à Klivans-van Melkebeek). Même si vous dérandomisez Valiant-Vaizarni, cela ne donne que le résultat que je mentionne ci-dessus - vous n'obtiendrez pas P = NP à moins d'avoir un algorithme qui pourrait résoudre la satisfiabilité avec des témoins uniques.

Lance Fortnow

P^{\oplus P} = B P P^{\oplus P}

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

P = B P P

$P=BPP$

P^{\oplus P} = B P P^{\oplus P}

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

22

Juste pour référence, je suis tombé sur ce document vraiment intéressant aujourd'hui, qui montre qu'une réduction déterministe est peu probable:

Dell, H., Kabanets, V., Watanabe, O., et van Melkebeek, D. (2012). Le lemme d'isolement de Valiant-Vazirani est-il améliorable? ECCC TR11-151

Ils soutiennent que cela n'est possible que si NP est contenu dans P / poly.

Henry Yuen
la source

Dérandomiser Valiant-Vazirani?

Réponses: