# Is $EVEN-SAT$ $NP$-hard?

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!

• 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$. Jul 22 '20 at 10:52

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

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}$$

• 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. Jul 22 '20 at 13:30