$\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, 2023 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, 2023 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, 2023 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, 2023 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, 2023 at 21:23


Your Answer

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