<p>Just for reference, I stumbled across this really interesting paper today, which gives evidence that a deterministic reduction is unlikely: </p>

<blockquote>
  <p>Dell, H., Kabanets, V., Watanabe, O., &amp; van Melkebeek, D. (2012). Is the Valiant-Vazirani Isolation Lemma Improvable? <em>ECCC <a href="http://eccc.hpi-web.de/report/2011/151/">TR11-151</a></em></p>
</blockquote>

<p>They argue that this is not possible unless NP is contained in P/poly.</p>

CC BY-SA 3.0
2011-11-09T21:13:08.850Z
2014-03-09T06:01:02.233Z
2014-03-09T06:01:02.233Z
Henry Yuen
<p>Under the right derandomization assumptions (see <a href="http://dx.doi.org/10.1145/301250.301428">Klivans-van Melkebeek</a>) you get the following: There is a polytime computable $f(\phi)=(\psi_1,\ldots,\psi_k)$ s.t. for all $\phi$,</p>

<ul>
<li>If $\phi$ is satisfiable then at least one of the $\psi_i$ has exactly one satisfying assignment.</li>
<li>If $\phi$ is not satisfiable then all of the $\psi_i$ are unsatisfiable.</li>
</ul>

<p>You need k polynomial in then length of $\phi$. Probably can't be done for $k=1$.</p>

CC BY-SA 3.0
2017-11-09T11:38:57.193Z
@LanceFortnow does $P=BPP$ imply Vazirani-Valiant isolation lemma can be derandomized and thus $P=BPP$ imply deterministic reduction to $SAT$ which would give $P=NP$?
Turbo
CC BY-SA 3.0
2017-11-09T14:46:14.013Z
No. You need a stronger assumption than P = BPP to derandomize Valiant-Vazirani (again I refer you to Klivans-van Melkebeek). Even if you do derandomize Valiant-Vaizarni this only gives the result I mention above--you wouldn't get P = NP unless you had an algorithm that could solve satisfiability with unique witnesses.
Lance Fortnow
CC BY-SA 3.0
2017-11-17T10:31:02.963Z
@LanceFortnow Just to be clear. Can we get $P^{\oplus P}=BPP^{\oplus P}$ by just $P=BPP$ or is it essential that (with the state of knowledge we have) it is likely that we need to get to derandomize VV to get to $P^{\oplus P}=BPP^{\oplus P}$ (this is a slightly different query than asking if just if P=BPP gives deterministic reduction SAT since it may not be essential that VV is needed at all in the first place to get NP in BPP^{oplus P}).
Turbo
CC BY-SA 3.0
2011-07-29T14:51:34.947Z
2011-07-29T14:51:34.947Z
Lance Fortnow
<p>The <a href="http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem">Valiant-Vazirani</a> theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an unsatisfiable formula - then <strong>NP=RP</strong>. This theorem is proved by showing that UNIQUE-SAT is <strong>NP</strong>-hard under <em>randomized</em> reductions.</p>

<p>Subject to plausible derandomization conjectures, the Theorem can be strengthened to "an efficient solution to UNIQUE-SAT implies <strong>NP = P</strong>". </p>

<p>My first instinct was to think that implied there exists a <em>deterministic</em> reduction from 3SAT to UNIQUE-SAT, but it's not clear to me how this particular reduction can be derandomized. </p>

<p>My question is: what is believed or known about "derandomizing reductions"? Is it/should it be possible? What about in the case of V-V? </p>

<p>Since UNIQUE-SAT is complete for <strong>PromiseNP</strong> under randomized reductions, can we use a derandomization tool to show that "a deterministic polynomial time solution to UNIQUE-SAT implies that <strong>PromiseNP = PromiseP</strong>? </p>

CC BY-SA 3.0
2011-07-29T12:15:55.033Z
As for the last paragraph, PromiseP=PromiseNP is equivalent to P=NP.
Tsuyoshi Ito
<cc.complexity-theory><reductions><derandomization><unique-solution>
Derandomizing Valiant-Vazirani?
Henry Yuen
# Derandomizing Valiant-Vazirani?

(Asked by: username_0 on 2011-07-29)

The [Valiant-Vazirani](http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem) theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an unsatisfiable formula - then **NP=RP**. This theorem is proved by showing that UNIQUE-SAT is **NP**-hard under *randomized* reductions.

Subject to plausible derandomization conjectures, the Theorem can be strengthened to "an efficient solution to UNIQUE-SAT implies **NP = P**".

My first instinct was to think that implied there exists a *deterministic* reduction from 3SAT to UNIQUE-SAT, but it's not clear to me how this particular reduction can be derandomized.

My question is: what is believed or known about "derandomizing reductions"? Is it/should it be possible? What about in the case of V-V?

Since UNIQUE-SAT is complete for **PromiseNP** under randomized reductions, can we use a derandomization tool to show that "a deterministic polynomial time solution to UNIQUE-SAT implies that **PromiseNP = PromiseP**?

**Tags:** cc.complexity-theory, reductions, derandomization, unique-solution

> **Comments:**
> **username_1**: As for the last paragraph, PromiseP=PromiseNP is equivalent to P=NP.  

---

## 2 answers

### Answer by username_2 on 2011-07-29. Score: 34 | Accepted answer

Under the right derandomization assumptions (see [Klivans-van Melkebeek](http://dx.doi.org/10.1145/301250.301428)) you get the following: There is a polytime computable $f(\phi)=(\psi\_1,\ldots,\psi\_k)$ s.t. for all $\phi$,

* If $\phi$ is satisfiable then at least one of the $\psi\_i$ has exactly one satisfying assignment.
* If $\phi$ is not satisfiable then all of the $\psi\_i$ are unsatisfiable.

You need k polynomial in then length of $\phi$. Probably can't be done for $k=1$.

> **Comments:**
> **username_3**: @LanceFortnow does $P=BPP$ imply Vazirani-Valiant isolation lemma can be derandomized and thus $P=BPP$ imply deterministic reduction to $SAT$ which would give $P=NP$?  
> **username_2**: No. You need a stronger assumption than P = BPP to derandomize Valiant-Vazirani (again I refer you to Klivans-van Melkebeek). Even if you do derandomize Valiant-Vaizarni this only gives the result I mention above--you wouldn't get P = NP unless you had an algorithm that could solve satisfiability with unique witnesses.  
> **username_3**: @LanceFortnow Just to be clear. Can we get $P^{\oplus P}=BPP^{\oplus P}$ by just $P=BPP$ or is it essential that (with the state of knowledge we have) it is likely that we need to get to derandomize VV to get to $P^{\oplus P}=BPP^{\oplus P}$ (this is a slightly different query than asking if just if P=BPP gives deterministic reduction SAT since it may not be essential that VV is needed at all in the first place to get NP in BPP^{oplus P}).  

---

### Answer by username_0 on 2011-11-09. Score: 24

Just for reference, I stumbled across this really interesting paper today, which gives evidence that a deterministic reduction is unlikely:

> Dell, H., Kabanets, V., Watanabe, O., & van Melkebeek, D. (2012). Is the Valiant-Vazirani Isolation Lemma Improvable? *ECCC [TR11-151](http://eccc.hpi-web.de/report/2011/151/)*

They argue that this is not possible unless NP is contained in P/poly.


---

