32

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?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Henry Yuen
  • 3,798
  • 1
  • 21
  • 33

2 Answers2

32

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

Lance Fortnow
  • 8,681
  • 44
  • 59
  • @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 Nov 09 '17 at 11:38
  • 1
    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 Nov 09 '17 at 14:46
  • @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 Nov 17 '17 at 10:31
22

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.

Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
Henry Yuen
  • 3,798
  • 1
  • 21
  • 33