1
$\begingroup$

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!

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ XOR-SAT is equivalent to solving a system of linear equations mod 2, which can be done in polynomial time using Gaussian elimination. $\endgroup$
    – Sasho Nikolov
    Commented Jan 10, 2014 at 14:51
  • $\begingroup$ 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. $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Jan 10, 2014 at 14:58
  • 2
    $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Commented Jan 10, 2014 at 15:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Juho
    Commented Jan 10, 2014 at 15:02
  • 3
    $\begingroup$ You can also always use Schaefer's theorem, which completely classifies binary CSP problems as being in P or NP-complete. $\endgroup$
    – Sasho Nikolov
    Commented Jan 10, 2014 at 15:07

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.