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: $$Phileft(mathbf xright)={hugewedge}_{i}^{n}C_i, forall_{C_i} left.C_i=(p oplus q)right|_{left(pin mathbf x veeneg pinmathbf xright),left(qin mathbf x veeneg qinmathbf xright)} $$ The $text{2-XOR-SAT}$ problem is to find a satisfying assignment of $mathbf x$ that would make $Phileft(mathbf xright)=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 $Phileft(mathbf xright)=T$.
Asked By : Realz Slaw
Answered By : Realz Slaw
- 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.
- Collect all the connected components of this graph.
- 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.
- 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 : http://cs.stackexchange.com/questions/16682 Ask a Question Download Related Notes/Documents
