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

Question

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!

Answer 1

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

Answer 2

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