How hard is it to solve SAT if the promise is that it has an odd number of solutions? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T05:27:08Z http://mathoverflow.net/feeds/question/21016 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21016/how-hard-is-it-to-solve-sat-if-the-promise-is-that-it-has-an-odd-number-of-soluti How hard is it to solve SAT if the promise is that it has an odd number of solutions? domotorp 2010-04-11T15:39:42Z 2012-08-30T08:39:42Z <p><a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">SAT</a> 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?</p> <p>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.</p> http://mathoverflow.net/questions/21016/how-hard-is-it-to-solve-sat-if-the-promise-is-that-it-has-an-odd-number-of-soluti/21026#21026 Answer by Ryan Williams for How hard is it to solve SAT if the promise is that it has an odd number of solutions? Ryan Williams 2010-04-11T19:09:26Z 2010-04-12T02:24:17Z <p><strong>UPDATED</strong> (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:</p> <blockquote> <p>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)</p> </blockquote> <p>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.</p> <p>--</p> <p><strong>(UPDATE: Some stuff got deleted here, as it is no longer relevant to the current version of the question)</strong></p> <p>--</p> <p>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.</p> <p>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 <strong>entire polynomial time hierarchy</strong> 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$.)</p> http://mathoverflow.net/questions/21016/how-hard-is-it-to-solve-sat-if-the-promise-is-that-it-has-an-odd-number-of-soluti/105916#105916 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? Vladimír Čunát 2012-08-30T08:39:42Z 2012-08-30T08:39:42Z <p>A simpler way to the answer is via the fact that you can easily increase the number of solutions exactly by one.</p> <p>$\varphi'(x_1, \dotsc, x_n, \ z) := \left( \bar z \ \&amp; \ \varphi(x_1, \dotsc, x_n) \right) \vee (z \ \&amp; \ \bar x_1 \&amp; \dots \&amp; \bar x_n)$</p>