# Hardness of XSAT

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!

• XOR-SAT is equivalent to solving a system of linear equations mod 2, which can be done in polynomial time using Gaussian elimination. Jan 10, 2014 at 14:51
• I hadn't noticed that the problem can be defined either with disjunctive clauses requiring an odd numbers of literals to be true, or with clauses requiring exactly one literal to be true. I am interested in the latter formulation. I rephrased the question adequately, apologies for missing this initially. Sasho Nikolov: This means that this is not the same thing as solving a system of linear equations in the Boolean ring.
– a3nm
Jan 10, 2014 at 14:58
• I think you mean EXACT SAT (XSAT) or if each clause has 3 literals "one in three" SAT (1-in-3 SAT)... it is NP-complete. The easy reduction is from exact cover in which every subset is a variable and the clauses represent the elements. Jan 10, 2014 at 15:00
• XSAT and 1-in-3 SAT are standard names for what Marzio describes. If this is indeed what you are looking for, have a look at the PhD thesis of Schmidt.
– Juho
Jan 10, 2014 at 15:02
• You can also always use Schaefer's theorem, which completely classifies binary CSP problems as being in P or NP-complete. Jan 10, 2014 at 15:07

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.