Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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$?


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

Asked By : Realz Slaw

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

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback