0
$\begingroup$

3SAT with the additional condition that exactly 1 or 3 literals must evaluate to 1.

$\endgroup$
4
$\begingroup$

No. This problem is equivalent to XOR-3SAT, in which we interpret each clause as $x \oplus y \oplus z$, where $\oplus$ is the XOR operator, and ask whether it's possible to find values for all variables so that each clause is true. XOR-SAT can be solved in polynomial time using Gaussian elimination, with all arithmetic done modulo 2 (i.e., in the finite field $GF(2)$).

$\endgroup$
2
$\begingroup$

By Schafer's Dichotomy Theorem, if a clause is expressible as a system of linear equations over Zmod2, it is in P. Thus it would not be NP-Complete.

$\endgroup$
1
  • $\begingroup$ Using the subjunctive ("if ..." and then "it would not be") gives me the impression that you're talking about a hypothetical situation contrary to reality. How about "These clauses are expressible as a system of linear equations over Z mod 2, so by SDT, the problem is not NP-Complete." $\endgroup$ May 25 '21 at 0:22

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