1
$\begingroup$

Vazirani-Valiant reduction is a randomized reduction from $SAT$ to unambiguous $SAT$.

1. Is $P=BPP$ strong enough to derandomize Vazirani-Valiant reduction?

2. If not what other ingredients are necessary to derandomize Vazirani-Valiant reduction?

The above two are addressed in Derandomizing Valiant-Vazirani?. However we can still ask whether there is a possibility of $P$ is not $BPP$ and still if it would be possible to derandomize Vazirani-Valiant.

  1. Is $P=BPP$ necessary to derandomize Vazirani-Valiant reduction?

  2. If not what would derandomizing Vazirani-Valiant reduction tell about $P=BPP$?

$\endgroup$
  • 2
    $\begingroup$ The following question might be helpful: cstheory.stackexchange.com/questions/7552/… $\endgroup$ – Or Meir Apr 27 '17 at 21:57
  • 1
    $\begingroup$ I believe 1 and 2 are basically a duplicate of the question Or pointed to, and are essentially answered there. I suggest to focus the question down to 3 and 4, and just point out as background that the other question essentially answers the opposite direction. $\endgroup$ – Joshua Grochow Apr 28 '17 at 3:31
  • $\begingroup$ @JoshuaGrochow ok I will update. $\endgroup$ – Turbo Apr 28 '17 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.