I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-time algorithm $R$ such that $R(\varphi) = (\psi_1, \dots, \psi_k)$ with $k$ polynomial in the size of $\varphi$, such that

  • if $\varphi$ is satisfiable, then at least one of the $\psi_i$ has exactly one satisfying assignment;
  • if $\varphi$ is unsatisfiable, then every $\psi_i$ is unsatisfiable.

Looking at the existing proofs of the Valiant-Vazirani lemma (Arora-Barak, and some lecture notes online), they all use the pairwise independent hashing over either $GF(2)^n$ or $GF(2^n)$. My problem is that, as far as I can tell, in both of these setups when $\varphi$ is satisfiable, some of the formulas in $\psi_i$ might have multiple satisfying assignments -- it's just that one particular $\psi_i$ is guaranteed to have exactly one. I want to avoid this.

My question: Is it possible to obtain (possibly with a different family of hashing functions) a reduction where

  • if $\varphi$ is satisfiable, then all the $\psi_i$ have at most one satisfying assignment, and at least one of the $\psi_i$ is satisfiable;
  • if $\varphi$ is unsatisfiable, then every $\psi_i$ is unsatisfiable.

I know that different improvements on Valiant-Vazirani are unlikely, but this variation doesn't seem to be ruled out by those results, or at least I couldn't see that. Is it known whether this reduction is possible?

  • 4
    $\begingroup$ You could combine all the $\psi_i$ to a single formula with at most $k$ satisfying assignments. Thus, if such a deterministic reduction exists, then NP = FewP. $\endgroup$ Dec 1, 2023 at 11:40
  • $\begingroup$ @EmilJeřábek Thanks Emil; sad news for my problem but good to know it likely cannot be done. If you add it as an answer I'll accept it as solved! $\endgroup$ Dec 1, 2023 at 12:18
  • 2
    $\begingroup$ To be honest, I'm not sure how unlikely NP = FewP really is. Also, I feel my argument loses a lot of information; someone may figure out how to do better (perhaps it even implies NP = UP?). $\endgroup$ Dec 1, 2023 at 12:55
  • $\begingroup$ I assume P=BPP already implies UP=NP. And that implies FewP = NP. $\endgroup$
    – rus9384
    Dec 2, 2023 at 11:51
  • 1
    $\begingroup$ I do not know. The brief paragraph on p. 6 of the Dell et al. paper suggests that this is not known to imply serious consequences such as collapsing the PH, as otherwise they would surely mention it. $\endgroup$ Dec 4, 2023 at 9:52


Your Answer

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