29
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ As for the last paragraph, PromiseP=PromiseNP is equivalent to P=NP. $\endgroup$ – Tsuyoshi Ito Jul 29 '11 at 12:15
30
$\begingroup$

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

$\endgroup$
  • $\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 '17 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$ – Lance Fortnow Nov 9 '17 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 '17 at 10:31
22
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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