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

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

• @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. Nov 4 '13 at 1:44
• @D.W. You can re-ask the question to your original understanding so as not to waste an answer :D. Nov 4 '13 at 3:22
• How could an optimisation problem ever be in either class?
– Raphael
Nov 4 '13 at 19:19
• @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$" Nov 4 '13 at 19:22
• 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.
– 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.
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$.
• 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.