<p>I am interested in the following &quot;improvement&quot; of the Valiant-Vazirani reduction. As pointed out <a href="https://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani">here</a>, under the right derandomization assumptions one can obtain a deterministic polynomial-time algorithm <span class="math-container">$R$</span> such that <span class="math-container">$R(\varphi) = (\psi_1, \dots, \psi_k)$</span> with <span class="math-container">$k$</span> polynomial in the size of <span class="math-container">$\varphi$</span>, such that</p>
<ul>
<li>if <span class="math-container">$\varphi$</span> is satisfiable, then at least one of the <span class="math-container">$\psi_i$</span> has exactly one satisfying assignment;</li>
<li>if <span class="math-container">$\varphi$</span> is unsatisfiable, then every <span class="math-container">$\psi_i$</span> is unsatisfiable.</li>
</ul>
<p>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 <span class="math-container">$GF(2)^n$</span> or <span class="math-container">$GF(2^n)$</span>. My problem is that, as far as I can tell, in both of these setups when <span class="math-container">$\varphi$</span> is satisfiable, some of the formulas in <span class="math-container">$\psi_i$</span> might have multiple satisfying assignments -- it's just that one particular <span class="math-container">$\psi_i$</span> is guaranteed to have exactly one. I want to avoid this.</p>
<p><strong>My question:</strong> Is it possible to obtain (possibly with a different family of hashing functions) a reduction where</p>
<ul>
<li>if <span class="math-container">$\varphi$</span> is satisfiable, <strong>then all the <span class="math-container">$\psi_i$</span> have at most one satisfying assignment</strong>, and at least one of the <span class="math-container">$\psi_i$</span> is satisfiable;</li>
<li>if <span class="math-container">$\varphi$</span> is unsatisfiable, then every <span class="math-container">$\psi_i$</span> is unsatisfiable.</li>
</ul>
<p>I know that <a href="https://eccc.weizmann.ac.il//report/2011/151/" rel="noreferrer">different improvements on Valiant-Vazirani are unlikely</a>, 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?</p>

CC BY-SA 4.0
2023-12-01T11:40:01.647Z
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
CC BY-SA 4.0
2023-12-01T12:18:53.887Z
@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
CC BY-SA 4.0
2023-12-01T12:55:46.623Z
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
CC BY-SA 4.0
2023-12-02T11:51:59.520Z
I assume P=BPP already implies UP=NP. And that implies FewP = NP.
rus9384
CC BY-SA 4.0
2023-12-02T12:47:45.607Z
P = BPP is not known to imply UP = NP. Why would it?
Emil Jeřábek
CC BY-SA 4.0
2023-12-02T22:42:33.943Z
@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
CC BY-SA 4.0
2023-12-02T23:08:27.397Z
@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
CC BY-SA 4.0
2023-12-02T23:17:47.910Z
@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
CC BY-SA 4.0
2023-12-03T19:26:05.613Z
@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
CC BY-SA 4.0
2023-12-03T19:38:58.140Z
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
CC BY-SA 4.0
2023-12-04T09:19:23.907Z
@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
CC BY-SA 4.0
2023-12-04T09:52:26.997Z
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
<sat><counting-complexity><reductions><derandomization><unique-solution>
Variation of (derandomized) Valiant-Vazirani
Noel Arteche
# Variation of (derandomized) Valiant-Vazirani

(Asked by: username_0 on 2023-12-01)

I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out [here](https://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani), 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](https://eccc.weizmann.ac.il//report/2011/151/), 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?

**Tags:** sat, counting-complexity, reductions, derandomization, unique-solution
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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!  
> **username_1**: 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?).  
> **username_2**: I assume P=BPP already implies UP=NP. And that implies FewP = NP.  
> **username_1**: P = BPP is not known to imply UP = NP. Why would it?  
> **username_2**: @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.  
> **username_1**: @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}}$.  
> **username_2**: @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)$.  
> **username_2**: @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.  
> **username_1**: 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.  
> **username_0**: @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.  
> **username_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.  

---

## 0 answers

