<p>The polynomial hierarchy would collapse to the fourth level (indeed, the third, see below).</p>
<p><em>Proof</em>. First, we get that <span class="math-container">$\oplus P\subseteq \Sigma_2^P$</span>. This is because a <span class="math-container">$\Sigma_2^P$</span> machine can use its <span class="math-container">$\exists$</span> quantifier to guess a polynomial number of assignments and then, using its <span class="math-container">$\forall$</span> quantifier, verify that this list contains all of the formula's satisfying assignments. By Valiant-Vazirani we have <span class="math-container">$PH\subseteq BPP^{\oplus P}$</span>. We have <span class="math-container">$BPP\subseteq \Sigma_2^P$</span>, so we get <span class="math-container">$BPP^{\oplus P}\subseteq {\Sigma_2^P}^{\oplus P}\subseteq {\Sigma_2^P}^{\Sigma_2^P}=\Sigma_4^P=PH$</span>. <span class="math-container">$\square$</span></p>
<p>@Emil Jerábek gives a stronger argument; the polynomial hierarchy collapses to the third level. This is because counting assignments can be done in <span class="math-container">$P^{NP}$</span>, which is better than the <span class="math-container">$\Sigma_2^P$</span> method described above.</p>
<p><em>Proof.</em> We get <span class="math-container">$\oplus P\subseteq P^{NP}$</span>, because a <span class="math-container">$P^{NP}$</span> algorithm can count a formula's satisfying assignments, if it is polynomially-bounded. (algorithm below). Consequently, we get <span class="math-container">$PH\subseteq BPP^{\oplus P}\subseteq BPP^{P^{NP}}=BPP^{NP}\subseteq \left(\Sigma_2^P\right)^{NP}=\Sigma_3^P=PH$</span>.</p>
<p><strong>Algorithm</strong> [For counting satisfying assignments in <span class="math-container">$P^{NP}$</span>]<strong>.<span class="math-container">$\quad$</span></strong> Given a Boolean formula <span class="math-container">$\psi$</span>, query the oracle. If the formula is not satisfiable, return. Otherwise, find a satisfying assignment <span class="math-container">$x$</span> using <span class="math-container">$n$</span> more queries to the oracle. Remove the assignment, i.e., construct a new formula <span class="math-container">$\psi^\prime:=\psi\wedge \neg x$</span>. Repeat this procedure until the oracle returns ``not satisfiable''. This happens exactly after all the satisfying assignments have been &quot;removed&quot;. This procedure therefore runs in time polynomial in the number of satisfying assignments, which, by assumption, is polynomial.</p>
<p>The inclusion <span class="math-container">$\oplus P\subseteq P^{NP}$</span> is obtained by simply returning ``yes'' at the end of the computation if and only if the number of satisfying assignments is discovered to be odd. <span class="math-container">$\square$</span></p>
<p>Perhaps there are other consequences; I hope others can give some.</p>

CC BY-SA 4.0
2020-08-13T15:02:11.693Z
The conclusion is correct, but I don't see where you got $\mathrm{PH\subseteq RP^{\oplus P}}$. Unconditionally, it is only known that PH (and in fact, $\mathrm{Mod_2PH}$) is included in $\mathrm{BPP^{\oplus P}}$, or better yet, $\mathrm{BP\cdot\oplus P}$. On the other hand, counting a polynomial number of assignments can be done in $\mathrm{P^{NP}}$. Thus, all in all, you get that $\mathrm{Mod_2PH}$ collapses to $\mathrm{BP\cdot P^{NP}=BPP^{NP}\subseteq\Sigma^P_3\cap\Pi^P_3}$.
Emil Jeřábek
CC BY-SA 4.0
2020-08-13T15:50:43.920Z
@EmilJeřábek Yes, good catch, I edited it, and now the Valiant-Vazirani Theorem is used correctly. It is a good observation that counting can now be done in $P^{NP}$, so I added your argument to the answer (of course, feel free to move it to your own answer!)
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2020-08-13T16:03:24.077Z
Slightly better, (the parity of) the number of satisfying assignments when polynomially bounded can be found in $\mathrm{P^{\|NP}=P^{NP[\log]}}$, hence you get $\mathrm{\oplus P\subseteq P^{NP[\log]}}$  and the whole hierarchy collapses to $\mathrm{BPP^{NP[\log]}}$.
Emil Jeřábek
CC BY-SA 4.0
2020-08-13T16:42:16.583Z
@LieuweVinkhuijzen, EmilJeřábek Even if "thank you" comments are discouraged, let me thank both of you for your time.
Giorgio Camerani
CC BY-SA 4.0
2020-11-20T16:15:55.687Z
To make this even simpler, by definition the assumption puts $\oplus$ P in the class Few which is known to be in $P^{Few P}\subseteq P^{NP}$. (See https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#few)
Lance Fortnow
CC BY-SA 4.0
2020-08-13T13:46:58.907Z
2020-08-13T15:52:42.823Z
2020-08-13T15:52:42.823Z
Lieuwe Vinkhuijzen
<p>Suppose there is a reduction which, given a <span class="math-container">$\oplus \text{SAT}$</span> instance <span class="math-container">$\phi$</span>, returns another <span class="math-container">$\oplus \text{SAT}$</span> instance <span class="math-container">$\psi$</span> having all the following properties:</p>
<ul>
<li>The size of <span class="math-container">$\psi$</span> is polynomial in <span class="math-container">$|\phi|$</span></li>
<li><span class="math-container">$\psi$</span> has an odd number of satisfying assignments if and only if <span class="math-container">$\phi$</span> has an odd number of satisfying assignments</li>
<li>The number of satisfying assignments of <span class="math-container">$\psi$</span> is polynomial in <span class="math-container">$|\psi|$</span>.</li>
</ul>
<p>Unless I'm wrong, that would mean that having a <span class="math-container">$\mathbf{NP}$</span> oracle allowed to formulate polynomially many queries would somehow be equivalent in power to having a <span class="math-container">$\oplus \mathbf{P}$</span> oracle.</p>
<blockquote>
<p><strong>Question</strong><br />
What would be the consequences of the existence of such reduction? Which surprising collapses would happen, if any? Would any widely believed conjecture be disproven?</p>
</blockquote>

<cc.complexity-theory><complexity-classes><counting-complexity>
Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments
Giorgio Camerani
# Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

(Asked by: username_0 on 2020-08-13)

Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties:

* The size of $\psi$ is polynomial in $|\phi|$
* $\psi$ has an odd number of satisfying assignments if and only if $\phi$ has an odd number of satisfying assignments
* The number of satisfying assignments of $\psi$ is polynomial in $|\psi|$.

Unless I'm wrong, that would mean that having a $\mathbf{NP}$ oracle allowed to formulate polynomially many queries would somehow be equivalent in power to having a $\oplus \mathbf{P}$ oracle.

> **Question**  
> What would be the consequences of the existence of such reduction? Which surprising collapses would happen, if any? Would any widely believed conjecture be disproven?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

---

## 1 answers

### Answer by username_1 on 2020-08-13. Score: 3 | Accepted answer

The polynomial hierarchy would collapse to the fourth level (indeed, the third, see below).

*Proof*. First, we get that $\oplus P\subseteq \Sigma\_2^P$. This is because a $\Sigma\_2^P$ machine can use its $\exists$ quantifier to guess a polynomial number of assignments and then, using its $\forall$ quantifier, verify that this list contains all of the formula's satisfying assignments. By Valiant-Vazirani we have $PH\subseteq BPP^{\oplus P}$. We have $BPP\subseteq \Sigma\_2^P$, so we get $BPP^{\oplus P}\subseteq {\Sigma\_2^P}^{\oplus P}\subseteq {\Sigma\_2^P}^{\Sigma\_2^P}=\Sigma\_4^P=PH$. $\square$

@Emil Jerábek gives a stronger argument; the polynomial hierarchy collapses to the third level. This is because counting assignments can be done in $P^{NP}$, which is better than the $\Sigma\_2^P$ method described above.

*Proof.* We get $\oplus P\subseteq P^{NP}$, because a $P^{NP}$ algorithm can count a formula's satisfying assignments, if it is polynomially-bounded. (algorithm below). Consequently, we get $PH\subseteq BPP^{\oplus P}\subseteq BPP^{P^{NP}}=BPP^{NP}\subseteq \left(\Sigma\_2^P\right)^{NP}=\Sigma\_3^P=PH$.

**Algorithm** [For counting satisfying assignments in $P^{NP}$]**.$\quad$** Given a Boolean formula $\psi$, query the oracle. If the formula is not satisfiable, return. Otherwise, find a satisfying assignment $x$ using $n$ more queries to the oracle. Remove the assignment, i.e., construct a new formula $\psi^\prime:=\psi\wedge \neg x$. Repeat this procedure until the oracle returns ``not satisfiable''. This happens exactly after all the satisfying assignments have been "removed". This procedure therefore runs in time polynomial in the number of satisfying assignments, which, by assumption, is polynomial.

The inclusion $\oplus P\subseteq P^{NP}$ is obtained by simply returning ``yes'' at the end of the computation if and only if the number of satisfying assignments is discovered to be odd. $\square$

Perhaps there are other consequences; I hope others can give some.

> **Comments:**
> **username_2**: The conclusion is correct, but I don't see where you got $\mathrm{PH\subseteq RP^{\oplus P}}$. Unconditionally, it is only known that PH (and in fact, $\mathrm{Mod_2PH}$) is included in $\mathrm{BPP^{\oplus P}}$, or better yet, $\mathrm{BP\cdot\oplus P}$. On the other hand, counting a polynomial number of assignments can be done in $\mathrm{P^{NP}}$. Thus, all in all, you get that $\mathrm{Mod_2PH}$ collapses to $\mathrm{BP\cdot P^{NP}=BPP^{NP}\subseteq\Sigma^P_3\cap\Pi^P_3}$.  
> **username_1**: @EmilJeřábek Yes, good catch, I edited it, and now the Valiant-Vazirani Theorem is used correctly. It is a good observation that counting can now be done in $P^{NP}$, so I added your argument to the answer (of course, feel free to move it to your own answer!)  
> **username_2**: Slightly better, (the parity of) the number of satisfying assignments when polynomially bounded can be found in $\mathrm{P^{\|NP}=P^{NP[\log]}}$, hence you get $\mathrm{\oplus P\subseteq P^{NP[\log]}}$  and the whole hierarchy collapses to $\mathrm{BPP^{NP[\log]}}$.  
> **username_0**: @LieuweVinkhuijzen, EmilJeřábek Even if "thank you" comments are discouraged, let me thank both of you for your time.  
> **username_3**: To make this even simpler, by definition the assumption puts $\oplus$ P in the class Few which is known to be in $P^{Few P}\subseteq P^{NP}$. (See https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#few)  

---

