Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
Can you explain what SAT is? I gather it is not the standardized test... –  Andy Putman Apr 11 '10 at 15:52
6  
SAT is a standard name for the Boolean satisfiability problem. en.wikipedia.org/wiki/Boolean_satisfiability_problem –  Douglas Zare Apr 11 '10 at 16:23
2  
(I deleted my earlier comment to Andy, which was obviously too harsh and reactionary. Sincere apologies to Andy.) –  François G. Dorais Apr 11 '10 at 16:55
3  
Kevin- I think you missed the point of my comment. I certainly had no idea that there was a legitimate mathematical construction called SAT before reading this question (which is fine, I don't study complexity theory). Probably many other people didn't either, and if you don't know that, the title certainly looks like it could be spam. In that situation, it's very helpful to have a comment from a user I know pointing out that it's a standard term, so I don't have to worry about figuring that out. –  Ben Webster Apr 12 '10 at 0:54
2  
Well, in any case, I'm a bit dismayed that SAT is not as well-known by mathematicians --- or at least MO users --- as I feel it definitely should be... –  Kevin H. Lin Apr 22 '10 at 5:31
show 7 more comments

2 Answers

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

share|improve this answer
    
Thank you for your answer, unfortunately I was aware of all this and it does not exactly answer my question. I added a clarifying remark to the end of my question. –  domotorp Apr 11 '10 at 21:51
    
If you are aware of all the above, then your question is answered, no? Let "Odd-or-Zero-SAT" be the problem of "we promise an odd or zero number of solutions" and wish to solve satisfiability. The above shows the following. 1. "Odd-Or-Zero-SAT" randomly reduces to USAT, since SAT without the promise reduces to it. 2. "Odd-Or-Zero-SAT" deterministically reduces to SAT. Your question was: "can we prove that it is reducible to one of them?" –  Ryan Williams Apr 11 '10 at 23:29
    
You are right, but my question obviously should be whether it is equivalent to any of them. I've updated my question again. –  domotorp Apr 12 '10 at 0:48
    
Any further comments on my answer? –  Ryan Williams May 24 '10 at 9:14
add comment

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

share|improve this answer
    
We certainly can but why is it useful? I don't think this implies any reduction/hardness result. –  domotorp Aug 30 '12 at 12:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.