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$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The following question might be helpful: cstheory.stackexchange.com/questions/7552/… $\endgroup$
    – Or Meir
    Commented Apr 27, 2017 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
    Commented Apr 28, 2017 at 3:31
  • $\begingroup$ @JoshuaGrochow ok I will update. $\endgroup$
    – Turbo
    Commented Apr 28, 2017 at 16:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.