1
$\begingroup$

It is often stated that the MAX-XOR-SAT problem is NP-hard, and that likewise is the MAX-2-XOR-SAT problem. However, I cannot find a reduction from SAT to either of these problems, nor a proof of NP-hardness. Is one published anywhere?

$\endgroup$
3
$\begingroup$

MAX-2-XOR-SAT is a generalization of the more familiar problem MAX-CUT.

To see this, consider a graph $G=(V,E)$. We will have a variable $x_v$ for each $v \in V$, and a constraint $x_u \oplus x_v$ for each edge $(u,v) \in E$. We can identify a cut $S \subseteq V$ with a truth assignment by $S = \{ v \in V : x_v = 1 \}$. You can then check that the number of clauses satisfied is exactly the same as the number of edges cut by $S$.

$\endgroup$
  • $\begingroup$ OK, thank you! I had not realized that it remains NP-hard even if the clauses are monotone. $\endgroup$ – Mike Battaglia Nov 17 '18 at 19:48

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