2
$\begingroup$

I'm looking for an $NP$-hardness proof for the following variant of $SAT$:

$$ EVEN-SAT = \{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\} $$

I've been playing around with gadgets for a while, but I haven't been able to construct a reduction. Still, I feel like there should be one. Help!

$\endgroup$
  • 2
    $\begingroup$ It is not np-complete according my knowledge. It is in class of $mod_2 P$ (parity P) and it contained NP and it is contained in class of #P‌(counting P). $NP \subset parity P \subset \#P$. $\endgroup$ – Mohsen Ghorbani Jul 22 at 10:52
3
$\begingroup$

$\textsf{EvenSat}$ is $\oplus P$-Complete (pronounced "Parity $P$"). The way to see this is (i) that it is the complement of $\textsf{OddSat}$, which is "the" natural $\oplus P$-Complete problem in the same way $\textsf{Sat}$ is "the" natural $\mathcal{NP}$-Complete problem, and (ii) $\oplus P$ is closed under complement.

The Valiant-Vazirani Theorem gives a randomized Cook reduction (i.e., a many-one reduction) with a one-sided error probability of $\mathcal{O}(1/n)$ from $\textsf{Sat}$ to $\textsf{EvenSat}$. That is, $\textsf{EvenSat}$ is $\mathcal{NP}$-Hard under randomized reductions. This is why the Valiani-Vazirani Theorem is usually stated as $\mathcal{NP}\subseteq \mathcal{RP}^{\oplus P}$.

We have $\mathcal{RP}^{\oplus P}\subseteq P^{\#P}$, so VV's Theorem is a bit tighter than what you would get from Toda's Theorem.

It is unlikely that $\textsf{EvenSat}$ is $\mathcal{NP}$-Complete, because then the polynomial hierarchy collapses to the first level, $PH=NP$. It is an open question whether $NP$ and $\oplus P$ are comparable, so far there is only oracle evidence that they are incomparable. (I don't know whether it is generally conjectured that Valiant-Vazirani can be derandomized from $\mathcal{NP}\subseteq\mathcal{RP}^{\oplus P}$ to $\mathcal{NP}\subseteq \mathcal{P}^{\oplus P}$. In that case, since $P^{\oplus P}=\oplus P$, we would have $\mathcal{NP}\subseteq \oplus P$. If I read [1] correctly, then it is not generally conjectured, since it would collapse the polynomial hierarchy)

[1] Dell, Holger, et al. "Is Valiant–Vazirani’s isolation probability improvable?." computational complexity 22.2 (2013): 345-383.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

It is known that $NP \subset P^{\#P}$ according to Toda's theorem but right now your question "NP hardnes of even SAT" is an open problem. We know that $NP \subset BPP^{mod_2 SAT}$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks! It looks like I touched on something deep. So I guess it is very likely that there is no simple reduction from SAT to EVEN-SAT. And since EVEN-SAT is probably not in NP, there is no reduction the other way either. So the problems are incomparable in some sense. $\endgroup$ – Zur Luria Jul 22 at 13:30

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.