MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

Question

What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard?

To formalize this more precisely, let

$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$

where $\mathbf{x} = (x_1,\dots,x_m)$ and each clause $C_i$ is of the form $(x_i \oplus x_j)$ or $(x_i \oplus \neg x_j)$.

The $\text{2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that satisfies $\Phi$. This problem is in $P$, as it corresponds to a system of linear equations mod $2$.

The $\text{MAX-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that maximizes the number of clauses that are satisfied. The $\text{MIN-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that minimizes the number of clauses that are satisfied. What are the complexities of these problems?

Inspired by Is MIN or MAX-True-2-XOR-SAT NP-hard?

Answer 1

Sorry for answering an old post

The problem of determining if a MONOTONE-2-XOR-SAT (all clauses are of the kind $({x_i}\oplus x_j)$) instance is satisfiable can be reduced to the problem of determining if a graph is bipartite, see this.

To do that we create a graph $G$ with a node for each literal of the formula and we connect each literal with another if they are in the same clause (edges are clauses)

For instance:

If we have an unsatisfiable formula that is $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4) $

We have a graph like this:

that is not bipartite

There are three clauses that are satisfiable and so we have just to eliminate an edge

Now, we can reduce the problem of determining if we can find a maximum bipartite subgraph with $k$ vertex to the problem of determining if we can satisfy $k$ clauses in a MONOTONE-MAX-2XOR-SAT formula, see this. And the maximum bipartite subgraph problem is equivalent to max cut

To do the reduction we simply create a new literal for each vertex and we create a clause for each edge connecting two literals

For instance:

We have this graph,

We create the follwing formula $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5) $

So, if we can find an assignment that satisfies $k$ clauses that will mean that there is a bipartite subgraph with at least $k$ edges.

Answer 2

Where each clause is only given as $(x_i\oplus x_j)$, create a vertex for each literal $x_i$, create an edge between two vertices if there exists an XOR relationship between them. For the statement $x_i\oplus x_j$ to be true, it should satisfy $x_i\neq x_j$. Now we can adopt the vertex coloring problem (no two vertices connected by an edge are assigned the same color, we have additional constraint of 2 colors only if we want to satisfy the equation). The clause $x_i\oplus x_j$ is true iff the corresponding vertices have been assigned different colors in the graph.

If all the vertices of the graph can be colored using 2 colors and none of two vertices with a common edge share are assigned the same color then the equation is satisfiable.

But a graph is 2-colorable iff it is a bipartite graph. And determining whether a graph is bipartite can be done in polynomial time. Therefore the problem is in P, because if we can determine in polynomial time that the graph is bipartite graph then it is solvable, otherwise it is not solvable.