11
$\begingroup$

What is the complexity of MIN-2-XOR-SAT and 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?

$\endgroup$
5
$\begingroup$

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:

grafo no bipartito

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,

grafo no bipartito 2

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.

$\endgroup$
  • 1
    $\begingroup$ You should make the implication explicit: Since MAX-CUT is NP-Hard, the reduction to MAX-XORSAT means that it is NP-Hard as well. $\endgroup$ – Antimony Apr 17 at 22:07
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ But the problem statement allows to have both clauses $(x_i \oplus x_j)$ and $(x_k \oplus \neg x_l)$. I don't see how you intend to handle clauses of the second type. Are you trying to solve a special case where there are no clauses of the second type? Something else? Perhaps you can collapse/unify every pair of vertices $k,l$ such that there exists a clause $(x_k \oplus \neg x_l)$? $\endgroup$ – D.W. Sep 23 '15 at 16:45
  • 2
    $\begingroup$ This brings me to a more serious problem with your answer. The problem is not to determine whether the formula is satisfiable; the problem is to identify an assignment that satisfies the maximum/minimum number of clauses. Your algorithm only tests whether the formula is satisfiable. Thus, it solves 2-XOR-SAT, but it doesn't solve MIN-2-XOR-SAT or MAX-2-XOR-SAT -- but I already knew that 2-XOR-SAT is in P, as explained in the question. Have I misunderstood something? $\endgroup$ – D.W. Sep 23 '15 at 16:48
  • $\begingroup$ Thank you, I have made the correction, that my answer applies only the clause is given by $x_i\oplus x_k$ $\endgroup$ – jcod0 Sep 23 '15 at 16:49
  • 1
    $\begingroup$ But I still don't see how this addresses my second comment. You've solved a special case of a problem that I wasn't asking about. In short, this answer doesn't answer the question that I asked. $\endgroup$ – D.W. Sep 23 '15 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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