6

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?

Noel Arteche
  • 988
  • 6
  • 12
  • 4
    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. – Emil Jeřábek Dec 01 '23 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! – Noel Arteche Dec 01 '23 at 12:18
  • 2
    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?). – Emil Jeřábek Dec 01 '23 at 12:55
  • I assume P=BPP already implies UP=NP. And that implies FewP = NP. – rus9384 Dec 02 '23 at 11:51
  • P = BPP is not known to imply UP = NP. Why would it? – Emil Jeřábek Dec 02 '23 at 12:47
  • @EmilJeřábek Actually, I guess that depends on whether a $UP^{RP}$ machine would be allowed to call the oracle whenever it can't decide whether the formula is satisfiable or not. This would be some inversion of Valiant-Vazirani theorem. But then in both cases the theorem does not guarantee a polynomial runtime. Only the expected runtime is polynomial, as is with ZPP. – rus9384 Dec 02 '23 at 22:42
  • @rus9384 ??? You seem to be completely confused. Even if the Valiant–Vazirani reduction produced a formula with one satisfying assignment with high probability (rather than only $1/n$ or so), it would be a randomized reduction to a (promise) UP problem (i.e., it would place NP in $\mathrm{RP^{promiseUP}}$), not a UP Turing reduction to an RP problem ($\mathrm{UP^{RP}}$). P = BPP does not in any way derandomize $\mathrm{RP^{promiseUP}}$. – Emil Jeřábek Dec 02 '23 at 23:08
  • @EmilJeřábek Oh, right, you'd need to find a way to make a BPP machine output just one bit of the formula in such a way that building a formula one by one with polynomially many oracle queries constructs an unambiguous formula with a probability $\ge 1/poly(n)$. – rus9384 Dec 02 '23 at 23:17
  • @EmilJeřábek okay, thought about this a bit more: if P=BPP, then FUP contains FBPP, which means a UP machine needs no oracle to construct an unambiguous formula either way, just call the Valiant-Vazirani algorithm internally, without referring to oracles. – rus9384 Dec 03 '23 at 19:26
  • I’m sorry, but what you are saying does not make any sense. The “Valiant–Vazirani algorithm” is an RP algorithm with a promiseUP oracle. It does not involve any UP machine, and it does not involve any unrelativized BPP or FBPP algorithm, which is the only thing that P = BPP allows you to derandomize. – Emil Jeřábek Dec 03 '23 at 19:38
  • @EmilJeřábek That's fair, I hadn't thought about NP = UP. It'd be interesting to see such a collapse is possible assuming this reduction; thought about it for a while but couldn't make it work. In any case, are there any known consequences of either NP = FewP or NP = UP? I found some oracle separations, but not much more. – Noel Arteche Dec 04 '23 at 09:19
  • 1
    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. – Emil Jeřábek Dec 04 '23 at 09:52

0 Answers0