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

  • $\begingroup$ @D.W. "maximize or minimize the number of true values in $\mathbf x$". Sorry for the confusion, I changed all the names to {MIN,MAX}-True-2-XOR-SAT. $\endgroup$ – Realz Slaw Nov 4 '13 at 1:44
  • $\begingroup$ @D.W. You can re-ask the question to your original understanding so as not to waste an answer :D. $\endgroup$ – Realz Slaw Nov 4 '13 at 3:22
  • $\begingroup$ How could an optimisation problem ever be in either class? $\endgroup$ – Raphael Nov 4 '13 at 19:19
  • $\begingroup$ @Raphael class NP-hard includes optimization problems. As for in P, I modified the question to say "... or that it (the decision version) is in $P$" $\endgroup$ – Realz Slaw Nov 4 '13 at 19:22
  • $\begingroup$ I guess that depends on the exact definition; but my comment was more intended to keep future readers (and you) on their toes. I did expect that you know what you are doing. $\endgroup$ – Raphael Nov 4 '13 at 19:25
  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$.

  • 1
    $\begingroup$ If you like, you can simplify this slightly, by building a graph on $m$ vertices instead of $2m$ vertices, i.e., one vertex for each variable $x_i$ instead of one vertex for each literal. Add an edge between $x_i$ and $x_j$ whenever you have a clause that mentions both $x_i$ and $x_j$ (whether positively or negatively). From there, you can continue with steps 2--4 of your algorithm; the rest follows similarly. $\endgroup$ – D.W. Nov 4 '13 at 3:22

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.