How hard is it to solve SAT if the promise is that it has an odd number of solutions?

2010-04-11T15:39:42Z

SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known to be NP-complete (except if we allow randomized reductions). What if we promise an odd number of solutions? The complexity must of course lie between the above two but can we prove that it is deterministically reducible to USAT or that SAT is deterministically reducible to it?

Remark. Of course I mean that we promise an odd or zero number of solutions. Or, another related problem would be, to find a solution under the promise. For related results see the excellent "survey" answer by Ryan.

Answer by Ryan Williams for How hard is it to solve SAT if the promise is that it has an odd number of solutions?

2010-04-11T19:09:26Z

UPDATED (after the question got changed): All right... your new questions are open questions in complexity theory, as far as I know. There has been some work on derandomizing the Valiant-Vazirani theorem, under reasonable hardness assumptions. A reference:

Adam Klivans, Dieter van Melkebeek: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM J. Comput. 31(5): 1501-1526 (2002)

So, under some plausible circuit lower bound assumptions, there is a deterministic polynomial time reduction from SAT to USAT. This would give a deterministic reduction from SAT to "Odd-or-Zero-SAT" as well as a deterministic reduction from "Odd-or-Zero-SAT" to USAT.

(UPDATE: Some stuff got deleted here, as it is no longer relevant to the current version of the question)

Despite all this, there is an extremely related problem that should be of interest to you. The problem "Parity-SAT" (often written as $\oplus SAT$ in the literature) is the problem of determining whether or not a given Boolean formula has an odd number of assignments. It is well-studied, and is complete for the class $\oplus P$ which contains all languages of the form {$x ~|~ \text{there are an odd number of accepting computation paths in}~N(x)$}, where $N$ is a nondeterministic polynomial time machine.

Now, by the Valiant-Vazirani Theorem (which I suspect you know, since you mentioned USAT) we have $$SAT ~\leq_R~ \oplus SAT,$$ where $\leq_R$ denotes a randomized polytime reduction. Hence $\oplus SAT$ is "hard" under randomized reductions. It is not known if $NP = \oplus P$, or $UP = \oplus P$. But, as the Valiant-Vazirani Theorem suggests, you can do a hell of a lot with randomized polynomial time and an oracle for $\oplus P$. We are still figuring out everything you can do. Toda's Theorem tells us that the entire polynomial time hierarchy is in $BPP^{\oplus P}$. It could be that even $PSPACE$ is in $BPP^{\oplus P}$. Another interesting fact due to Papadimitriou and Zachos is that $\oplus P^{\oplus P} = \oplus P$. That is, an oracle for $\oplus P$ is superfluous if you already have the power of $\oplus P$. This follows from the observation that the XOR of a bunch of XORs is still an XOR. (Similarly, $P^{P} = P$, but it is not known or believed that $NP^{NP} = NP$.)

Answer by Vladimír Čunát for How hard is it to solve SAT if the promise is that it has an odd number of solutions?

2012-08-30T08:39:42Z

A simpler way to the answer is via the fact that you can easily increase the number of solutions exactly by one.

$\varphi'(x_1, \dotsc, x_n, \ z) := \left( \bar z \ \& \ \varphi(x_1, \dotsc, x_n) \right) \vee (z \ \& \ \bar x_1 \& \dots \& \bar x_n)$

How hard is it to solve SAT if the promise is that it has an odd number of solutions? - MathOverflow

How hard is it to solve SAT if the promise is that it has an odd number of solutions?

Answer by Ryan Williams for How hard is it to solve SAT if the promise is that it has an odd number of solutions?

Answer by Vladimír Čunát for How hard is it to solve SAT if the promise is that it has an odd number of solutions?