11
$\begingroup$

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.

$\endgroup$
9
  • 3
    $\begingroup$ Can you explain what SAT is? I gather it is not the standardized test... $\endgroup$ Apr 11, 2010 at 15:52
  • 7
    $\begingroup$ SAT is a standard name for the Boolean satisfiability problem. en.wikipedia.org/wiki/Boolean_satisfiability_problem $\endgroup$ Apr 11, 2010 at 16:23
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ben Webster
    Apr 12, 2010 at 0:54
  • 2
    $\begingroup$ When I asked the above question, I was not trying to cast aspersions on the question. Rather, I thought it sounded interesting, and I wanted to know what SAT was! I tried google, but since the SAT is also the initials of the US college admissions test, that didnt't help. I think that it is good MO practice to expand out abbreviations so as to help interested nonspecialists look things up. In fields closer to my own, people have asked for this many times (for instance, I remember someone asking what a PPAV was when "everyone" knows that it is a principally polarized abelian variety!). $\endgroup$ Apr 12, 2010 at 2:45
  • 3
    $\begingroup$ 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... $\endgroup$ Apr 22, 2010 at 5:31

2 Answers 2

11
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Apr 11, 2010 at 21:51
  • $\begingroup$ 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?" $\endgroup$ Apr 11, 2010 at 23:29
  • $\begingroup$ You are right, but my question obviously should be whether it is equivalent to any of them. I've updated my question again. $\endgroup$
    – domotorp
    Apr 12, 2010 at 0:48
  • $\begingroup$ Any further comments on my answer? $\endgroup$ May 24, 2010 at 9:14
0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ We certainly can but why is it useful? I don't think this implies any reduction/hardness result. $\endgroup$
    – domotorp
    Aug 30, 2012 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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