$\oplus$SAT is the problem of deciding if the number of satisfying assignments to a CNF formula is odd (and is the standard complete problem for the class $\oplus$P, or Parity-P).

Suppose we have a fast algorithm for SAT. Is there anything known about what this algorithm would imply for $\oplus$SAT?

More concretely, suppose that P=NP. Does this imply that $\oplus$P collapses to some (presumably) smaller complexity class?

  • 2
    $\begingroup$ No such collapse is known. For example, there exists an oracle $A$ such that $\mathrm P^A=\mathrm{NP}^A$ and $\oplus\mathrm P^A=\mathrm{EXP}^A$ (doi.org/10.1109/CCC.1999.766280). $\endgroup$ Oct 2 at 12:03
  • $\begingroup$ Thanks Emil, but could you expand a bit on how conclusive such a result is? In particular, it seems to be unknown whether $\oplus$P$\subseteq$PP. If, for example, we had a result that says P=NP$\Rightarrow \oplus$P$\subseteq$PP, would that contradict the oracle result you cited? $\endgroup$ Oct 2 at 12:45
  • $\begingroup$ This is not a “conclusive result”. It is an illustration of the fact of nature that as of now, P = NP is not known to imply any nontrivial collapse of $\oplus$P. It is possible that someone will prove such a collapse in the future; the oracle result formally only implies that any proof of such a result has to be nonrelativizing. Indeed, we hope that some day someone will prove $\mathrm{P\ne NP}$, and therefore all implications of the form “$\mathrm{P=NP}\implies\cdots$", including, e.g., $\mathrm{P=NP\implies P=\oplus P}$. $\endgroup$ Oct 2 at 13:11
  • $\begingroup$ Suppose that X is some class for which X$\subseteq\oplus$P is known and such that X$^A$=$\oplus$P$^A$ (for the oracle A of the paper you cited). In this case, proving that P=NP$\Rightarrow$X=$\oplus$P wouldn't need to be nonrelativizing, no? $\endgroup$ Oct 2 at 13:27
  • 1
    $\begingroup$ OK, thanks for putting me back on track, I guess. Since we're forgetting about the oracle result, do you have any other justification for your claim that nothing like this is known? (I realize of course that it's hard to prove a negative...) $\endgroup$ Oct 2 at 21:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.