TransWikia.com

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

Computer Science Asked by Zur Luria on November 23, 2021

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!

2 Answers

$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}subseteqmathcal{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.

Answered by Lieuwe Vinkhuijzen on November 23, 2021

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

Answered by Mohsen Ghorbani on November 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP