The standard NP-hard SAT problem is the problem of Boolean satisfiability of conjunctions of clauses, where clauses are disjunctions of literals.I am interested in the problem of the Boolean satisfiability of conjunctions of exclusive clauses, where exclusive clauses is an exclusive disjunction of multiple literals. By exclusive disjunction of literals, I do not mean $l_1 \oplus \ldots \oplus  l_n$, which would require an odd number of literals to be true; I mean that the clause is true iff exactly one literal of the clause is true. (Of course, the literals can be positive or negative, i.e., $l = x$ or $l = \neg x$.)Is there a reference to justify that it is also NP-hard, or a straightforward reduction to prove it?I had a look in Wikipedia and in the Garey-Johnson, to no avail. Thanks in advance for your help!
Hardness of XSAT
cc.complexity theory;reference request;np hardness;sat
Exact SAT (XSAT) is NP-hard by a reduction from the exact hitting set problem (or, equivalently, exact set cover), even when all literals are positive. Encode the set $X$ to a set of positive literals, and each subset to a clause. Now, solving Exact SAT amounts to deciding whether some subset of the positive literals is such that every clause contains exactly one positive literal.