<p><span class="math-container">$\oplus$</span>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 <span class="math-container">$\oplus$</span>P, or Parity-P).</p>
<p>Suppose we have a fast algorithm for SAT. Is there anything known about what this algorithm would imply for <span class="math-container">$\oplus$</span>SAT?</p>
<p>More concretely, suppose that P=NP. Does this imply that <span class="math-container">$\oplus$</span>P collapses to some (presumably) smaller complexity class?</p>

CC BY-SA 4.0
2023-10-02T12:03:53.027Z
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$ (https://doi.org/10.1109/CCC.1999.766280).
Emil Jeřábek
CC BY-SA 4.0
2023-10-02T12:45:47.767Z
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?
Michael Lampis
CC BY-SA 4.0
2023-10-02T13:11:46.700Z
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}$.
Emil Jeřábek
CC BY-SA 4.0
2023-10-02T13:27:20.787Z
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?
Michael Lampis
CC BY-SA 4.0
2023-10-02T14:25:20.910Z
You know what? Forget about the oracle result. It clearly just derailed you off the track. As of now, P = NP is not known to imply any collapse of $\oplus\mathrm P$, period.
Emil Jeřábek
CC BY-SA 4.0
2023-10-02T21:23:20.640Z
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...)
Michael Lampis
<cc.complexity-theory><complexity-classes><counting-complexity>
Do fast satisfiability algorithms imply fast algorithms for parity SAT?
Michael Lampis
# Do fast satisfiability algorithms imply fast algorithms for parity SAT?

(Asked by: username_0 on 2023-10-02)

$\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?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity
> **Comments:**
> **username_1**: 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$ (https://doi.org/10.1109/CCC.1999.766280).  
> **username_0**: 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?  
> **username_1**: 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}$.  
> **username_0**: 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?  
> **username_1**: You know what? Forget about the oracle result. It clearly just derailed you off the track. As of now, P = NP is not known to imply any collapse of $\oplus\mathrm P$, period.  
> **username_0**: 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...)  

---

## 0 answers

