Theoretical Computer Science
cc.complexity-theory reductions derandomization unique-solution
Updated Thu, 16 Jun 2022 04:27:53 GMT

Derandomizing Valiant-Vazirani?


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?



Solution

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

Comments (3)

  • +0 – @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$? — Nov 09, 2017 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. — Nov 09, 2017 at 14:46  
  • +0 – @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}). — Nov 17, 2017 at 10:31  

External Links

External links referenced by this document:

References