1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Emil Jeřábek Aug 13 at 15:02
  • $\begingroup$ @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!) $\endgroup$ – Lieuwe Vinkhuijzen Aug 13 at 15:50
  • 1
    $\begingroup$ 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]}}$. $\endgroup$ – Emil Jeřábek Aug 13 at 16:03
  • $\begingroup$ @LieuweVinkhuijzen, EmilJeřábek Even if "thank you" comments are discouraged, let me thank both of you for your time. $\endgroup$ – Giorgio Camerani Aug 13 at 16:42
  • $\begingroup$ 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 complexityzoo.uwaterloo.ca/Complexity_Zoo:F#few) $\endgroup$ – Lance Fortnow Nov 20 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.