MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 updated answer, since question changed

Note that if you are promised that there are an odd number of satisfying assignments and wish to solve satisfiability,

UPDATED (after the satisfiability problem under this promise is trivialquestion got changed): there is always a "yes" answer! Also it is very easy to "extract" a satisfying assignment for problems with that promise, given a SAT oracleAll right... Simply plug your new questions are open questions in "false" for some variable, call an oracle for SATcomplexity theory, and if that doesn't work then "true" must workas far as I know. Proceed similarly for all There has been some work on derandomizing the variables. This produces a satisfying assignmentValiant-Vazirani theorem, under reasonable hardness assumptions. In other wordsA reference:

Adam Klivans, it is very easy to reduce Dieter van Melkebeek: Graph Nonisomorphism Has Subexponential Size Proofs Unless the problem of finding a satisfying assignment to SATPolynomial-Time Hierarchy Collapses.

Maybe you are interested in the complexity of finding a satisfying assignment when you are promised that the number is odd? Note this is a problem in $TFNP$ SIAM J. Comput. 31(5): 1501-1526 (total function $NP$), since 2002)

So, under some plausible circuit lower bound assumptions, there is always a satisfying assignment. As you know with deterministic polynomial time reduction from SAT to USAT, this promise is not very strong: . This would give a deterministic reduction from SAT to "odd" could simply be Odd-or-Zero-SAT" as well as a deterministic reduction from "exactly one"Odd-or-Zero-SAT" to USAT.And if this problem were easy

--

(UPDATE: Some stuff got deleted here, then by a randomized reduction you could claim that as it is also easy no longer relevant to find a satisfying assignment when an arbitrary formula is satisfiable.the current version of the question)

--
show/hide this revision's text 2 added some more explanation

Note that if you are promised that there are an odd number of satisfying assignments and wish to solve satisfiability, the satisfiability problem under this promise is trivial: there is always a "yes" answer! Also it is very easy to "extract" a satisfying assignment for problems with that promise, given a SAT oracle. Simply plug in "false" for some variable, call an oracle for SAT, and if that doesn't work then "true" must work. Proceed similarly for all the variables. This produces a satisfying assignment.

StillIn other words, it is very easy to reduce the problem of finding a satisfying assignment to SAT.

Maybe you are interested in the complexity of finding a satisfying assignment when you are promised that the number is odd? Note this is a problem in $TFNP$ (total function $NP$), since there is always a satisfying assignment. As you know with USAT, this promise is not very strong: "odd" could simply be "exactly one". And if this problem were easy, then by a randomized reduction you could claim that it is also easy to find a satisfying assignment when an arbitrary formula is satisfiable.

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$.)
show/hide this revision's text 1

Note that if you are promised that there are an odd number of satisfying assignments and wish to solve satisfiability, the satisfiability problem under this promise is trivial: there is always a "yes" answer! Also it is very easy to "extract" a satisfying assignment for problems with that promise, given a SAT oracle. Simply plug in "false" for some variable, call an oracle for SAT, and if that doesn't work then "true" must work. Proceed similarly for all the variables. This produces a satisfying assignment.

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