# Variation of (derandomized) Valiant-Vazirani

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?

• 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. Commented Dec 1, 2023 at 11:40
• @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! Commented Dec 1, 2023 at 12:18
• 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?). Commented Dec 1, 2023 at 12:55
• I assume P=BPP already implies UP=NP. And that implies FewP = NP. Commented Dec 2, 2023 at 11:51
• 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. Commented Dec 4, 2023 at 9:52