Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Is MIN or MAX-True-2-XOR-SAT NP-hard?

, ,
Problem Detail:

Is there a proof or reference that $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$?

Let:

$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,\\ \forall_{C_i} \left.C_i=(p \oplus q)\right|_{\left(p\in \mathbf x \vee\neg p\in\mathbf x\right),\left(q\in \mathbf x \vee\neg q\in\mathbf x\right)}$$

The $\text{2-XOR-SAT}$ problem is to find a satisfying assignment of $\mathbf x$ that would make $\Phi\left(\mathbf x\right)=T$. This is in $P$, as it can be encoded in a set of linear equations mod $2$.

The $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ problems are to maximize or minimize the number of true values in $\mathbf x$, respectively, subject to the constraint that $\Phi\left(\mathbf x\right)=T$.

#### Answered By : Realz Slaw

1. Build an implication graph, in the style of solving $\text{2-SAT}$: each literal gets a $x_i$ node and a $\neg x_i$ node. Each clause is turned into implications, each implication gives a directed edge from the antecedent-node to the consequence-node.

2. Collect all the connected components of this graph.

3. Each connected component will have only $2$ states: since each relationship is of the forms $x_i=x_j$ or $x_i \ne x_j$; this means if you assign even a single variable, the entire component will be force-assigned. This means you only have $2$ choices for each component.

4. For each connected component, greedily choose the assignment state that will increase (for $\text{MAX}$; decrease for $\text{MIN}$) the truth values in $\mathbf x$.

Question Source : http://cs.stackexchange.com/questions/16682