5
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 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$
    – Emil Jeřábek
    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$
    – Michael Lampis
    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$
    – Emil Jeřábek
    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$
    – Michael Lampis
    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$
    – Michael Lampis
    Oct 2 at 21:23

0

Reset to default

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.