# NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT [duplicate]

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?

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$$.