<p>Vazirani-Valiant reduction is a randomized reduction from <span class="math-container">$SAT$</span> to unambiguous <span class="math-container">$SAT$</span>.</p>

<p><s>1. Is <span class="math-container">$P=BPP$</span> strong enough to derandomize Vazirani-Valiant reduction?</s></p>

<p><s>2. If not what other ingredients are necessary to derandomize Vazirani-Valiant reduction?</s></p>

<p>The above two are addressed in <a href="https://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani">Derandomizing Valiant-Vazirani?</a>. However we can still ask whether there is a possibility of <span class="math-container">$P$</span> is not <span class="math-container">$BPP$</span> and still if it would be possible to derandomize Vazirani-Valiant.</p>

<ol start="3">
<li><p>Is <span class="math-container">$P=BPP$</span> necessary to derandomize Vazirani-Valiant reduction? </p></li>
<li><p>If not what would derandomizing Vazirani-Valiant reduction tell about <span class="math-container">$P=BPP$</span>?</p></li>
</ol>

CC BY-SA 3.0
2017-04-27T21:57:17.550Z
The following question might be helpful: https://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani?rq=1
Or Meir
CC BY-SA 3.0
2017-04-28T03:31:16.640Z
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.
Joshua Grochow
CC BY-SA 3.0
2017-04-28T16:55:19.160Z
@JoshuaGrochow ok I will update.
Turbo
<big-picture><derandomization>
P=BPP and derandomizing Vazirani-Valiant?
Turbo
# P=BPP and derandomizing Vazirani-Valiant?

(Asked by: username_0 on 2017-04-27)

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?](https://cstheory.stackexchange.com/questions/7552/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.

3. Is $P=BPP$ necessary to derandomize Vazirani-Valiant reduction?
4. If not what would derandomizing Vazirani-Valiant reduction tell about $P=BPP$?

**Tags:** big-picture, derandomization

> **Comments:**
> **username_1**: The following question might be helpful: https://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani?rq=1  
> **username_2**: 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.  
> **username_0**: @JoshuaGrochow ok I will update.  

---

## 0 answers

