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)