The Valiant-Vazirani 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?

  • 4
    $\begingroup$ As for the last paragraph, PromiseP=PromiseNP is equivalent to P=NP. $\endgroup$ Jul 29, 2011 at 12:15

2 Answers 2


Under the right derandomization assumptions (see Klivans-van Melkebeek) 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$.

  • $\begingroup$ @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$? $\endgroup$
    – Turbo
    Nov 9, 2017 at 11:38
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 9, 2017 at 14:46
  • $\begingroup$ @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}). $\endgroup$
    – Turbo
    Nov 17, 2017 at 10:31

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

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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.