<p>Exact SAT (XSAT) is NP-hard by a reduction from the <a href="https://en.wikipedia.org/wiki/Exact_hitting_set#Exact_hitting_set" rel="nofollow">exact hitting set</a> 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.</p>

CC BY-SA 3.0
2014-01-10T15:25:06.557Z
2014-01-10T15:25:06.557Z
Antoine Amarilli 'a3nm'
<p>The standard NP-hard SAT problem is the problem of <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">Boolean satisfiability</a> of conjunctions of clauses, where clauses are disjunctions of literals.</p>

<p>I am interested in the problem of the Boolean satisfiability of conjunctions of <em>exclusive</em> clauses, where exclusive clauses is an <em>exclusive</em> 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 <em>exactly one</em> literal of the clause is true. (Of course, the literals can be positive or negative, i.e., $l = x$ or $l = \neg x$.)</p>

<p>Is there a reference to justify that it is also NP-hard, or a straightforward reduction to prove it?</p>

<p>I had a look in Wikipedia and in the Garey-Johnson, to no avail. Thanks in advance for your help!</p>

CC BY-SA 3.0
2014-01-10T14:51:57.363Z
XOR-SAT is equivalent to solving a system of linear equations mod 2, which can be done in polynomial time using Gaussian elimination.
Sasho Nikolov
CC BY-SA 3.0
2014-01-10T14:58:59.740Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-01-10T15:00:13.983Z
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.
Marzio De Biasi
CC BY-SA 3.0
2014-01-10T15:02:45.170Z
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](http://kups.ub.uni-koeln.de/3129/2/Dissertation_Endversion.pdf).
Juho
CC BY-SA 3.0
2014-01-10T15:07:50.077Z
You can also always use Schaefer's theorem, which completely classifies binary CSP problems as being in P or NP-complete.
Sasho Nikolov
CC BY-SA 3.0
2014-01-10T15:14:01.920Z
OK, I think I got it, it's straightforwardly NP-hard through exact hitting set. Trying to write it.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-01-13T15:43:48.963Z
Marzio De Biasi: Yeah, thanks, just needed to wait for some time for this information to become available. Now done.
Antoine Amarilli 'a3nm'
<cc.complexity-theory><reference-request><np-hardness><sat>
Hardness of XSAT
Antoine Amarilli 'a3nm'
# Hardness of XSAT

(Asked by: username_0 on 2014-01-10)

The standard NP-hard SAT problem is the problem of [Boolean satisfiability](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) 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!

**Tags:** cc.complexity-theory, reference-request, np-hardness, sat

> **Comments:**
> **username_1**: XOR-SAT is equivalent to solving a system of linear equations mod 2, which can be done in polynomial time using Gaussian elimination.  
> **username_0**: 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. username_1: This means that this is not the same thing as solving a system of linear equations in the Boolean ring.  
> **username_2**: 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.  
> **username_3**: 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](http://kups.ub.uni-koeln.de/3129/2/Dissertation_Endversion.pdf).  
> **username_1**: You can also always use Schaefer's theorem, which completely classifies binary CSP problems as being in P or NP-complete.  
> **username_0**: OK, I think I got it, it's straightforwardly NP-hard through exact hitting set. Trying to write it.  
> **username_0**: username_2: Yeah, thanks, just needed to wait for some time for this information to become available. Now done.  

---

## 1 answers

### Answer by username_0 on 2014-01-10. Score: 2 | Accepted answer

Exact SAT (XSAT) is NP-hard by a reduction from the [exact hitting set](https://en.wikipedia.org/wiki/Exact_hitting_set#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.


---

